Longest Palindromic Substring

Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Naive Way: 遍历一遍，对每一个字符都左右遍历直至不对称。这样算法复杂度是O(n^2)。这道题作为DP的教材题目当时也是有想过用Opt(i,j)来表示s[i..j]是否为回文。

 

逻辑为：

// base case

For all i:

opt[i,i] = 1;

opt[i,j] = 0; (i > j)

// iteration 

opt[i,j] = opt[i+1,j-1] && s[i]==s[j]

 

 现在想想这个方法不仅也是O(n^2）的run time,而且还要用O(n^2)的space,真不是一个好方法。下面是我第一次的做法，写得非常不好，应该用begin index和end index记录substring而不是每一次都替换它。而且需要分奇数和偶数。

 

public String longestPalindrome(String s) {
        String result = s;
        int longest = 0;
        for(int i = 1;i < s.length();i++){
            int j = 1;
            if(s.charAt(i-1)==s.charAt(i)){
                while(i-1-j >=0 && i+j < s.length()){
                    if(s.charAt(i-1-j)!=s.charAt(i+j))
                        break;
                    j++;
                }
                if(2*j > longest){
                    longest = 2*j;
                    result = s.substring(i-j,i+j);
                }
            }
            j = 1;
            while(i-j >= 0 && i+j < s.length()){
                if(s.charAt(i-j)!=s.charAt(i+j))
                    break;
                j++;
            }
            if(2*j-1 > longest){
                longest = 2*j-1;
                result = s.substring(i-j+1,i+j);
            }
        }
        return result;
    }

Improved Way:这个世界上有了人类，就必然有牛一点的人类。1337c0d3r在博客中详细讲解了O(n)的实现方法，同时还推荐了一个中国人写得解法：

  Manacher's ALGORITHM: O(n)时间求字符串的最长回文子串 

 

我是看这个中国人的博客所写的做法，很清楚。用自己的语言写一写这个方法，加深印象。

 

1.首先对字符串做一个预处理：

baaaa

#b#a#a#a#a#

这样做在不改变回文关系的情况下，将奇数和偶数进行了统一。因为不存在连续两个相同字符的情况，所有回文都变成了奇数。

2.然后设置一个pivot，这个pivot是当前覆盖范围最长的字符所在的位置，一开始的时候应该要先初始第一个字符的最长回文为1，然后当前覆盖范围最长的就是第一个字符了。

3.看pivot(s[p])的覆盖范围是否包含了现在正在处理的字符s[i]：

如果不包含，说明pivot(s[p])的信息不能提供给当前字符s[i]有用的信息，老老实实左右匹配算该字符的最长回文数。

如果包含，因为知道pivot(s[p])两侧是对称的，那么当前位置s[i]在pivot的镜面位置s[2*p-i] =s[j]上的字符应该是一样的。不只是这样，可以知道，从s[j]到s[p]和从s[p]到s[i]这段距离内的字符是对称的，那么在pivot的覆盖范围内从s[i]向右也应该有部分字符是与s[j]向左是对称的。

4. 接步骤3中第二个如果，在pivot的覆盖范围内从s[i]往右也应该有部分字符是与s[j]向左是对称的，

如果我们知道s[j]的覆盖范围要小于这个距离（即s[j]的覆盖范围完全在pivot的覆盖范围之内），s[i]的往右去的那一部分就应该跟s[j]往左去的那一部分完全对称。可以得到  s[i]的覆盖范围=s[j]的覆盖范围

如果s[j]的覆盖范围要大于这个距离（即pivot的覆盖范围是与s[j]的覆盖范围有交集），那么我们知道在pivot的覆盖范围内，s[j]所覆盖的与s[i]所覆盖的范围是一样的。那么s[i]再往右去的覆盖范围就无法得知，此时依然要在这个基础老老实实匹配。

例如：当前黑体位置是pivot=5，拥有最大覆盖范围4，我们要求index=6位置的覆盖范围。红体是pivot覆盖范围的边界。

 

首 先，6是在（5-4, 5+4]）= （1,9）这个范围内的，说明pivot的覆盖范围能为我们提供一些信息。然后镜面的位置是4，它的覆盖范围（4-3,4+3） = （1,7）是在pivot的覆盖范围内的，而对应当前位置6，可以得知（6-3,6+3） = （3,9）这个范围和（4-3,4+3）的内容是完全一致的，因为（1,9）范围内的内容是对称的。

0  1  2  3  4  5  6  7  8  9  10

 

#  b  #  a  #  a  #  a  #   a   # 

 

1  2  1  2  3  4 ？

6的覆盖范围至少是3。

 

 

0  1  2  3  4  5  6  7  8  9  10

 

#  b  #  a  #  a  #  a  #   a   # 

 

1  2  1  2  3  4  3

但 是因为pivot=5的覆盖范围正好和镜像4的覆盖边界重合，我们不能确定6的当前覆盖范围(3,9)往右的情况。所以还不能直接写6的覆盖范围是3。后 面的还得老老实实匹配，但是可以在3的基础上进行匹配了。比如(3,9)是当前范围，下一个要匹配的就是3和9，然后是2和10...

0  1  2  3  4  5  6  7  8  9  10

 

#  b  #  a  #  a  #  a  #   a   # 

 

1  2  1  2  3  4  3

 

 

 最后匹配到2和10发现不能再继续，填写6位置处新的覆盖范围5。

0  1  2  3  4  5  6  7  8  9  10

 

#  b  #  a  #  a  #  a  #   a   #  

1  2  1  2  3  4  5

 

 

最后发现新的覆盖范围(6-5,6+5) = (1,11)已经超出就的最大覆盖范围,pivot的(1,9)，所以把6设为新的pivot。 

 

0  1  2  3  4  5  6  7  8  9  10

 

#  b  #  a  #   a  #  a  #   a   #  

1  2  1  2  3   4  5

 

 

然后继续下一个字符。

我写的这个太粗燥，估计大家可能看不懂，建议点击上面的链接去看看详细的解释。

下面是我根据该方法写的代码：

public class Solution {
    public String longestPalindrome(String s) {
        String str = preProcess(s);
        int f[] = new int[str.length()];
        int longest = 0;
        int begin = 0, end = 0;
        
        // initialize
        int p = 0; // pivot
        f[0] = 1;
        
        // general case
        for(int i = 1;i < str.length();i++){
            
            int right = p+f[p]; // get pivot's right most range
            f[i] = 1; // if pivot's range not covers i, start from 1
            if(right > i){ // if pivot's range covers i
                if(right - i > f[2*p-i]) // if mirror's range is within pivot's range
                    f[i] = f[2*p-i];
                else // if pivot's range gives out but the right side still not decided
                    f[i] = right - i;
            }
            
            while(i-f[i] >= 0 && i + f[i] < str.length()){
                if(str.charAt(i-f[i])!=str.charAt(i+f[i]))
                    break;
                f[i]++;
            }
            
            if(f[i] + i > f[p] + p)
                p = i;
        }
        
        for(int i = 0;i < f.length;i++){
            if(f[i] > longest){
                longest = f[i];
                begin = (i-f[i]+1)/2;
                end = (i+f[i]-1)/2;
            }
        }
        
        return s.substring(begin,end);
    }
    
    private String preProcess(String s){
        StringBuilder str = new StringBuilder();
        str.append('#');
        for(int i = 0;i < s.length();i++){
            str.append(s.charAt(i));
            str.append('#');
        }
        return str.toString();
    }
}