给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1:

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2:

输入: "cbbd"
输出: "bb"

https://leetcode-cn.com/problems/longest-palindromic-substring/

解法1

暴力法很容易想到,我们使用双层循环固定字串的起止位置,然后对字串判断是否为回文串。双层循环的时间复杂度是O(n^2),再嵌套一个回文判断循环O(n),时间复杂度为O(n^3)。但是这里,我们不打算使用暴力法,因为很容易想到,码代码就好了。

我们在这里使用了一种方法,我称之为中心扩展法,那么我们先来定义中心。中心是由单个字符或连续多个相同的字符组成的子串。我们第一次扫描,找到字符串所有的中心。然后遍历每个中心的左右两边的字符,如果相同就继续扩展直到遇到边界或两边字符不同,这样我们就找到了一个回文串。题目要求最长回文串,我们就遍历每个中心,都做相同的扩展操作,选取找到的最长的回文串既是答案。需要特殊注意的是,中心本身也是回文串,也是潜在的答案。

代码中我们使用List<int[]>来存放找到的中心列表,int[0]与int[1]分别是中心的起止索引,都是闭区间。

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0)
            return s;
        /*

        babad
        aabbaax
        aba
        aaaa
        abbbbaaaa
        cbbd
   abbba
        我们将字符串中多个连续字符称为一个centric,如果字符s[i]和下一个字符s[i+1]不相同,那么s[i]作为一个centric
        从centric出发,先看左右两边第一个字符是否相等,若相等,看左右两边第二个字符是否相等。。。直到不相等或遇到边界
         */

        String ans = "";
        List<int[]> centricList = new ArrayList<>();
        int pos = 0;
        char lastCh = s.charAt(0);
        int lastPos = 0;

        // 寻找centric
        while (pos < s.length()) {
            if (lastCh != s.charAt(pos)) {
                centricList.add(new int[]{lastPos, pos - 1});
                lastPos = pos;
                lastCh = s.charAt(pos);
            }
            pos++;
        }

        centricList.add(new int[]{lastPos, s.length() - 1});

        for (int[] bound : centricList) {
            int l = bound[0] - 1;
            int r = bound[1] + 1;

            // centric本身也是潜在的答案
            if (bound[1] - bound[0] + 1 > ans.length())
                ans = s.substring(bound[0], bound[1] + 1);
            // 从centric两边扩展
            while (l >= 0 &amp;&amp; r < s.length()) {
                if (s.charAt(l) != s.charAt(r))
                    break;
                if (r - l + 1 > ans.length())
                    ans = s.substring(l, r + 1);
                l--;
                r++;
            }
        }

        return ans;
    }
}

解法2

方法分析

解法1是我自己想的,解法2、3都是源于LeetCode官方题解。解法2首先对字符串s逆序(reverse),记为s’。我们对字符串s与s’求最长公共子串

例如,s=”acbcd”, s’=”dcbca”。求s与s’的最长公共子串为”cbc”,在这个例子中,这样的方法成功的求出了答案。我们再举一个例子,s=”abcdxydcba”, s’=”abcdyxdcba”。s与s’的最长公共子串是”abcd”,这显然不是回文子串。

问题出在哪呢?LeetCode题解说道“当s的其他部分中存在非回文子串的反向副本时,最长公共子串法就会失败”。我们来分析下,正是因为s中存在了非回文子串的反向副本,导致非回文子串出现在s’中。我们对s与s’求最长公共子串,也就把非回文子串取了出来。

举例分析:s=”[abcd]xy[dcba]”, s’=”[abcd]yx[dcba]”。s中第一个括号是[abcd],他的反向副本[dcba]同样在s中出现了。我们观察s中第二个中括号[dcba],在对s进行逆序操作后跑到了s’中第一个括号中。这样,我们对s与s’求最长公共子串就得到了错误的”abcd”。

那我们如何修正这样对情况,使得这个方法正确呢?我们只需要确保找到的最长公共子串的索引(indexOf)与最长公共子串的逆序的索引相同,就能保证找到的子串是反向的。(我认为这与判断找到的最长公共子串是否是回文串的条件是等价的,不对的话望指正

作者疑问

还有一个问题,真的只需要寻找最长公共子串,并且确定最长公共子串的索引与其逆序的索引相同就够了吗?

例如 s=”abacdfgdcaba”, s’=”abacdgfdcaba”。s与s’的最长公共子串为abacd,但其在s中的索引与其反向索引不同,一个是0,一个是7,所以该子串不是最长回文子串。可是,方法二所说的求s与s’的最长公共子串可只有一个啊,接下来没法玩了啊!!!。

那该方法说的是不是不准确啊,应该找出s与s’所有的公共子串,然后所有公共子串的索引与其逆序的索引是否相同。这么做不就和暴力法差不多了吗?暴力法是找到s所有的子串判断是否为回文串。这个方法是找到s与s’所有的公共子串,判断索引与其逆序的索引是否相同。

代码

好吧,带着疑问写代码。我的做法是求出s与s’所有的公共子串,然后求其索引与反向索引是否相同。运行了几个case答案是正确的,但是粘贴到LeetCode提示超时。这个方法不太可取,创建了大量的临时变量,还包含递归函数。

class Solution {
    String getLCS(int[][] mtx, int rid, int cid, String s1, StringBuilder builder) {
        if (rid < 0 || cid < 0 || mtx[rid][cid] == 0) {
            return builder.reverse().toString();
        }
        builder.append(s1.charAt(rid));
        return getLCS(mtx, rid - 1, cid - 1, s1, builder);
    }

    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0)
            return s;
        String s1 = s, s2 = new StringBuilder(s).reverse().toString();
        int[][] mtx = new int[s1.length()][s2.length()];

        String ans = "";


        for (int rid = 0; rid < s1.length(); rid++) {
            for (int cid = 0; cid < s2.length(); cid++) {
                if (s1.charAt(rid) == s2.charAt(cid)) {
                    // 填充第一行或第一列
                    if (rid == 0 || cid == 0)
                        mtx[rid][cid] = 1;
                    else { // 否则该位置由左上角而来
                        mtx[rid][cid] = mtx[rid - 1][cid - 1] + 1;
                    }

                    // 存在公共子串
                    if (mtx[rid][cid] != 0) {
                        String cs = getLCS(mtx, rid, cid, s1, new StringBuilder());
                        String rCs = new StringBuilder(cs).reverse().toString();

                        if (s1.indexOf(cs) == s1.indexOf(rCs) &amp;&amp; cs.length() > ans.length()) {
                            ans = cs;
                        }
                    }
                }
            }
        }

        return ans;
    }
}

解法3

解法三使用动态规划,这个方法源自LeetCode官方题解

状态转移方程:P(i, j) = S[i] == S[j] and P(i + 1, j – 1)

P(i, j)定义:如果字符串s的子串s[i, j]是回文串,则P(i, j)为true;否则P(i, j)为false。其中i与j是字符串的索引,都取闭区间。

很容易想到P(i, i)一定为true,因为s[i, i]就是s的第i个字符,单独的一个字符当然是回文。这是其中一个corner case。另一个case是 P(i, i+1) = S[i] == S[i+1],这个case覆盖了相邻两个字符串。这两个case的物理意义是分别处理len=1与len=2的回文串,以后遇到len=奇数或偶数的字符串,都可以推到len=1或len=2这两个case上。

我们再来分析下状态转移方程的物理意义。如果S[i]与S[j]相同,那么我们把左右两端“削去”后看看它是否是回文串,如果是的话我们把左右两端加上变成更长的串,也一定是回文串了。

举个例子,s=”a b a b a“。假设现在i=0,j=4,满足s[i] == s[j]。接下来我们把左右两个‘a’削去,看看bab是不是回文串。这个bab在使用动态规划算法时,实际上已经被提前算好了。显然P(1,3)=true。那么我们就能推出P(0, 4) = P(1, 3) && S[0] == S[4] = true。我们由之前发现的回文串“bab”推出了更长的回文串“ababa”。

在实现中,我们可以使用一个|s|x|s|的二维数组来存储这些boolean值。我们将二维数组的行索引作为子串的起始位置,列索引作为终止位置,均取闭区间。那么很容易想想,这个二维数组只有“右上三角”被使用。我们举一个例子,s=“ababa”。

ababa
aTFTFT
bTFTF
aTFT
bTF
aT

当我们填充好这个矩阵后,如何寻找最长回文子串呢?方法很简单,我们只需要按行扫描,寻找某一行两个True的位置相距最远即可。这个例子中,第一行的两个True相距最远,那么我们记住两个True的列号,根据列号对字符串s做substring操作就可以得到答案了。想想这是问什么呢?我们定义了行号是起始位置,列号是终止位置。如果固定了行号,也就是找到了起始位置。对于每个起始位置,我们找目前能发现的最长的回文子串。当s的每个起始位置被扫描了一边后,字符串s的最长回文子串也就被找到了。

下面我们放出代码,写的可能比较啰嗦但是结果是正确的。LeetCode上执行花了118ms,而解法1只花了27ms,因为解法3涉及到两次O(n^2)操作。

class Solution {

    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0)
            return s;

        /*

        P(i, j) = P(i + 1, j - 1) and S[i] == S[j]
                  false
        P(i, i) = true
        P(i, i+1) = S[i] == S[i+1]


              j
           A B A B
         A T F T F
      i  B   T F T
         A     T F
         B       T
           a b a b a
         a T F T F T
         b   T F T F
         a     T F T
         b       T F
         a         T

         */

        int len = s.length();
        boolean[][] dp = new boolean[len][len];

        // base case P(i, i) = True
        for (int i = 0; i < len; i++)
            dp[i][i] = true;

        // base case P(i, i+1) = s[i] == s[i+1]
        for (int i = 0; i < len - 1; i++) {
            dp[i][i + 1] = s.charAt(i) == s.charAt(i + 1);
        }

        for (int sLen = 2; sLen < len; sLen++) {
            int cid;
            for (int rid = 0; rid < len &amp;&amp; (cid = (rid + sLen)) < len; rid++) {
                if (s.charAt(rid) == s.charAt(cid)) {
                    dp[rid][cid] = dp[rid + 1][cid - 1];
                }
            }
        }

        // 故意这么赋初值来应对len=1的case。
        int start = len, end = 0;

        // 下面的代码通过扫描dp,寻找某一行两个true相聚最远的位置,将索引分别赋予start和end
        for (int rid = 0; rid < len; rid++) {
            int tmp = -1;
            for (int cid = 0; cid < len; cid++) {
                if (dp[rid][cid]) {
                    if (tmp == -1)
                        tmp = cid;

                    if (cid - tmp > end - start) {
                        start = tmp;
                        end = cid;
                    }
                }
            }
        }

        return s.substring(start, end + 1);
    }
}
pwrliang Algorithms, Dynamic Programming, String

Leave a Reply

Your email address will not be published. Required fields are marked *