长大后想做什么？做回小孩！

0%

LeetCode——最长回文子串

发表于 更新于 分类于 Valine：
本文字数： 2.9k

NO.5 最长回文子串 中等

Q8ZSII.png

思路一：暴力法 用两个for循环划分出所有子串，并依次判断划分出的子串是否为回文，如果是回文并且子串长度大于ans当前记录的值，就更新ans。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public String longestPalindrome(String s) {
    String ans="";
    int len=0;
    for (int i=0;i<s.length();i++){
        for (int j=i+1;j<s.length();j++){
            if (isPalindrome(s.substring(i,j))&&len<j-i+1){
                ans=s.substring(i,j);
                len=Math.max(len,ans.length());
            }
        }
    }
    return ans;
}

boolean isPalindrome(String s){
    for (int i=0;i<s.length()/2;i++){
        if (s.charAt(i)!=s.charAt(s.length()-1-i))
            return false;
    }
    return true;
}

时间复杂度:O(n^3)

思路二：扩展中心法 经过对回文特点的观察发现，回文都是中心对称的。所以我们可以从中心进行展开判断，一个长度为n的字符串中有2n-1个中心（因为回文长度有可能是基数或偶数，基数回文的中心有n个，如abc中心是b；偶数回文的中心有n-1个，如abbc中心是bb）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public String longestPalindrome(String s) {
//        如果是空串，则直接返回空串表示没有回文串
        if (s==null||s.length()<1)return "";
        int start=0,end=0;
        for (int i=0;i<s.length();i++){
//            判断i为中心的基数回文长度
            int len1=expandAroundCenter(s,i,i);
//            判断i，i+1为中心的偶数回文长度
            int len2=expandAroundCenter(s,i,i+1);
            int len=Math.max(len1,len2);
//            如果新回文串的长度大于之前的回文串长度，则更新
            if (len>end-start){
//                
                start=i-(len-1)/2;
                end=i+len/2;
            }
        }
//        因为substring()方法截取的范围是[起始索引,结束索引)，所以第二个参数需要+1
        return s.substring(start,end+1);
    }

    public int expandAroundCenter(String s,int left,int right){
//        当左标记大于等于0,且右标记小于输入串长，且当前左右标记的字符相等时，左右标记分别中心扩展
        while (left>=0&&right<s.length()&&s.charAt(left)==s.charAt(right)){
            left--;
            right++;
        }
//        返回以i或(i，i+1)为中心的回文串长度。
        return right-left-1;
    }

时间复杂度：O(n^2)

思路三：最长公共子串法(LCS) 回文是从左向右读和从右向左读都是一样的，所以我们可以将原字符串s倒置之后获得s’，然后取s和s’的最长公共子串ans作为最长回文子串。

用动态规划法求最长公共子串，大概思路是：1.申请一个二维数组arr[s.length][s’.length]。2.判断每个对应位置的字符是否相等，如果相等 arr[i][j]=arr[i-1][j-1]+1；当i=0或j=0时候单独分析，如果对应位置字符相等 arr[i][j]=1。(PS：arr[i][j]保存的就是公共子串的长度。)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public String longestPalindrome(String s) {
        if (s.equals(""))return "";
        String origin=s;
//        倒置原字符串
        String reverse=new StringBuffer(s).reverse().toString();
//        maxLen记录最长公共子序列，maxEnd记录最长公共子序列的结尾下标
        int maxLen=0,maxEnd=0;
//        分别以原字符串长度和倒置字符串长度来表示，是为了更直观的理解该二维数组
        int[][] arr=new int[origin.length()][reverse.length()];
//        双重循环遍历二维数组
        for (int i=0;i<origin.length();i++){
            for (int j=0;j<reverse.length();j++){
//                判断原字符串i位置字符和倒置字符串j位置字符是否相等
                if (origin.charAt(i)==reverse.charAt(j)){
                    if (i==0||j==0){//当i=0或j=0时候单独分析，如果对应位置字符相等 arr[i][j]=1
                        arr[i][j]=1;
                    }else{
                        arr[i][j]=arr[i-1][j-1]+1;
                    }
                }
//                如果当前公共子串长度比maxLen所记录的值更大，则更新最长公共子串的长度及其结束下标
                if (arr[i][j]>maxLen){
                    maxLen=arr[i][j];
                    maxEnd=i;
                }
            }
        }
        return s.substring(maxEnd-maxLen+1,maxEnd+1);
    }

当S=”abc435cba”，S’=”abc534cba”时，上述算法依然可以计算出最长公共子串”abc”来作为最长回文子串，这显然是不对的。对于这个问题的解决思路是：1.因为j一直指向倒置字符串中子串的末尾字符，可以先求出j指向的字符X倒置之前的下标beforeReverse=length-1-j。2.此时求出的beforeReverse是X在原字符串中的子串首位的下标，还需要加上当前子串的长度才是原字符串中子串末尾的下标e，即e=beforeReverse+arr[i][j]-1。3.因为i一直指向原字符串中子串的末尾字符，所以将e与i进行比较，如果相等，则说明当前找到的公共子串是回文子串。

例如，字符串倒置前后分别是S=”abc435cba”，S’=”abc534cba”，当i=2且j=2时，arr[2][2]=3,然后进行计算出beforeReverse=length-1-j=9-1-2=6，判断beforeReverse+arr[2][2]-1是否等于i，显然 6+3-1!=2，所以当前子串不是回文子串且不需要更新maxLen和maxEnd。

Qamn76.png

针对该思路，只需要在更新maxLen和maxEnd之前添加下标是否匹配的判断即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public String longestPalindrome(String s) {
        if (s.equals(""))return "";
        String origin=s;
//        倒置原字符串
        String reverse=new StringBuffer(s).reverse().toString();
//        maxLen记录最长公共子序列，maxEnd记录最长公共子序列的结尾下标
        int maxLen=0,maxEnd=0;
//        分别以原字符串长度和倒置字符串长度来表示，是为了更直观的理解该二维数组
        int[][] arr=new int[origin.length()][reverse.length()];
//        双重循环遍历二维数组
        for (int i=0;i<origin.length();i++){
            for (int j=0;j<reverse.length();j++){
//                判断原字符串i位置字符和倒置字符串j位置字符是否相等
                if (origin.charAt(i)==reverse.charAt(j)){
                    if (i==0||j==0){//当i=0或j=0时候单独分析，如果对应位置字符相等 arr[i][j]=1
                        arr[i][j]=1;
                    }else{
                        arr[i][j]=arr[i-1][j-1]+1;
                    }
                }
//                如果当前公共子串长度比maxLen所记录的值更大，则更新最长公共子串的长度及其结束下标
                if (arr[i][j]>maxLen){
                    int beforeReverse=origin.length()-1-j;
//					  添加下标是否匹配的判断                 
                    if (beforeReverse+arr[i][j]-1==i) {
                        maxLen = arr[i][j];
                        maxEnd = i;
                    }
                }
            }
        }
        return s.substring(maxEnd-maxLen+1,maxEnd+1);
    }

时间复杂度:O(n^2)

写到这里，利用LCS算法解决求最长回文子串的问题已经基本完成了,经过查阅资料和学习之后发现：其实可以使用一个一位数组即可，而不必使用上述的二维数组arr[][]。空间复杂度从之前的用二维数组时的O(n^2)降到了用一维数组后的O(n)。

例如还是上面的那个数组S=”abc435cba”，i=0，j=1、2、3、4、5、6、7、8更新了第一列；i=2j=1、2、3、4、5、6、7、8更新了第二列，以此类推直到i=8且j=8每一列都更新完毕。但是经过观察发现，每次更新时只需要参考前一列的值，更新第三列时，第一列的值就用不到了，所以只需要一个一维数组就可以了。但是，更新arr[i]的时候需要arr[i-1]的值，例如arr[3]=arr[2]+1，arr[4]=arr[3]+1，此时的arr[3]的信息已经被更新过了并不是”之前一列的信息了“，所以循环时j不能从0到8递增，应该倒过来，arr[8]=arr[7]+1、arr[7]=arr[6]+1。。。更新arr[8]时用arr[7]，用完之后才能去更新arr[7]：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public String longestPalindrome(String s) {
        if (s.equals(""))return "";
        String origin=s;
//        倒置原字符串
        String reverse=new StringBuffer(s).reverse().toString();
//        maxLen记录最长公共子序列，maxEnd记录最长公共子序列的结尾下标
        int maxLen=0,maxEnd=0;
//        分别以原字符串长度和倒置字符串长度来表示，是为了更直观的理解该二维数组
        int[] arr=new int[s.length()];
//        双重循环遍历二维数组
        for (int i=0;i<origin.length();i++){
            for (int j=reverse.length()-1;j>=0;j--){
//                判断原字符串i位置字符和倒置字符串j位置字符是否相等
                if (origin.charAt(i)==reverse.charAt(j)){
                    if (i==0||j==0){//当i=0或j=0时候单独分析，如果对应位置字符相等 arr[j]=1
                        arr[j]=1;
                    }else{
                        arr[j]=arr[j-1]+1;
                    }
                }else {//之前是二维数组每一列默认值就是0，现在是一维数组所以需要手动更新为0
                    arr[j]=0;
                }
//                如果当前公共子串长度比maxLen所记录的值更大，则更新最长公共子串的长度及其结束下标
                if (arr[j]>maxLen){
                    int beforeReverse=origin.length()-1-j;
                    if (beforeReverse+arr[j]-1==i) {
                        maxLen = arr[j];
                        maxEnd = i;
                    }
                }
            }
        }
        return s.substring(maxEnd-maxLen+1,maxEnd+1);
    }

思路四：Manacher算法 在扩展中心算法中，将奇数长度回文子串和偶数长度的回文子串分别进行了处理。本算法首先解决了奇数和偶数的问题，在每个字符间插入“#”，并且为了使得扩展的过程中，到边界后自动结束，在两端分别插入“^”和“$”，这样重心扩展的时候，判断两端字符是否相等时，如果到了边界就一定不会相等，从而结束循环（这里的“#”“^”“$”是字符串中不存在的字符）。并且，经过插入特殊字符处理后，字符串的长度永远都是奇数了。

1
2
3
4
例如，
	"aba" 扩展为 "^#a#b#a#$"
	"acca" 扩展为 "^#a#c#c#a#$"
	"cbcbccde" 扩展为 "^#c#b#c#b#c#c#d#e#$"

字符串扩展之后，我们申请一个数组p[]保存从中心扩展的最大个数，而这个数也刚好是去掉”#“之后原子串的长度。例如下图中下标为6的字符，p[6]=5,所以它是从左边扩展5个字符，相应的右边也是扩展5个字符，也就是“#c#b#c#b#c#”。而去掉“#”恢复到原来的子串，变成“cbcbc”，它的长度刚好也是5。

QawkCQ.png

求原字符串下标：用p的下标i减去p[i]，再除以2，就是原字符串的开头下标了。例如，我们找到上图中p[i]最大值为5，也就是回文串的最大长度是5，对应的下标是6，所以原子串在原字符串中的开头下标是（6-5）/2=0。所以我们只需要返回原字符串的第0到第（5-1）位就可以了。

既然已经知道了如何利用p[]数组巧妙地取得结果子串了，那么就要进行马拉车算法最重要的步骤了，即如何求p[]数组？

这一步是马拉车算法的精髓所在，充分利用的回文的对称性。用c表示回文子串的中心，用r表示回文子串的右边半径。所以r=c+p[i]。C 和 R 所对应的回文串是当前循环中 R 最靠右的回文串，而不一定是最长的回文串。

Q0m8Ld.png

用 i_mirror 表示当前需要求的第 i 个字符关于 C 对应的下标。 我们现在要求 P [ i ]，如果是用中心扩展法，那就向两边扩展比对就行了。但是我们其实可以利用回文串中心 C 的对称性。i 关于 C 的对称点是 i_mirror，P [ i_mirror ] = 3，所以 P [ i ] 也等于 3。

但是有三种情况将会造成直接赋值为 P [ i_mirror ] 是不正确的，下边一一讨论:

情况一：超出了 R

Q0mJeA.png

当我们要求 P [ i ] 的时候，P [ mirror ] = 7，而此时 P [ i ] 并不等于 7，为什么呢，因为我们从 i 开始往后数 7 个，等于 22，已经超过了最右的 R，此时不能利用对称性了，但我们一定可以扩展到 R 的，所以 P [ i ] 至少等于 R - i = 20 - 15 = 5，会不会更大呢，我们只需要比较 T [ R+1 ] 和 T [ R+1 ]关于 i 的对称点就行了，就像中心扩展法一样一个个扩展。

情况二：P [ i_mirror ] 遇到了原字符串的左边界

Q0mtot.png

此时P [ i_mirror ] = 1，但是 P [ i ] 赋值成 1 是不正确的，出现这种情况的原因是 P [ i_mirror ] 在扩展的时候首先是 “#” == “#”，之后遇到了 “^” 和另一个字符比较，也就是到了边界，才终止循环的。而 P [ i ] 并没有遇到边界，所以我们可以继续通过中心扩展法一步一步向两边扩展就行了。

情况三：i 等于了 R

此时我们先把 P [ i ] 赋值为 0，然后通过中心扩展法一步一步扩展就行了。

考虑 C 和 R 的更新
就这样一步一步的求出每个 P [ i ]，当求出的 P [ i ] 的右边界大于当前的 R 时，我们就需要更新 C 和 R 为当前的回文串了。因为我们必须保证 i 在 R 里面，所以一旦有更右边的 R 就要更新 R。

Q0mYdI.png

此时的 P [ i ] 求出来将会是 3，P [ i ] 对应的右边界将是 10 + 3 = 13，所以大于当前的 R，我们需要把 C 更新成 i 的值，也就是 10，R 更新成 13。继续下边的循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
public String longestPalindrome(String s) {
//        获取扩充后的字符串T
        String T=preProsess(s);
        int len=T.length();
        int[] p=new int[len];
        int c=0,r=0;
//        不需要判断前后边界字符“^"和“$”，所以循环范围是[1,len-1)
        for (int i=1;i<len-1;i++){
//            第i个字符关于c对称的下标
            int i_mirror=2*c-i;
            if (r>i){//如果i小于对称半径r
                p[i]=Math.max(r-i,p[i_mirror]);
            }else {
                p[i]=0;
            }

//            遇到三种特殊情况时，需要退化到中心扩展法
            while (T.charAt(i+1+p[i])==T.charAt(i-1-p[i])){
                p[i]++;
            }

//            判断是否需要更新c和r
            if (i+p[i]>r){
                c=i;
                r=p[i];
            }
        }
//        找出p[]数组中最大的值
        int currentIndex=0,maxLen=0;
        for (int i=0;i<p.length;i++){
            if (p[i]>maxLen){
                currentIndex=i;
                maxLen=p[i];
            }
        }

//        求子串首字符在原字符串中的下标
        int start=(currentIndex-maxLen)/2;
        return s.substring(start,start+maxLen);
    }
//    扩充字符串
    public String preProsess(String s){
        if (s.equals(""))return "$";
        String result="^";
        for (int i=0;i<s.length();i++){
            result+="#"+s.charAt(i);
        }
        result+="#$";
        return result;
    }

时间复杂度:O(n)

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github