找出字符串最大回文

题目

给定一个字符串 s，找到s中最长的回文字符串。可以假设s的最长长度是1000。 Example1 : Input: “babad” Output: “bab” Note: “aba” 也是可以的答案 Example2 : Input: “cbbd” Output: “bb”

解法

假设前i个字符最大的回文串长度是currLength，那么i+1个字符最大的回文长度计算方法是：

计算i+1-curLength-1到i+1是否为回文
计算i+1-curLength-2到i+1是否为回文
如果前两步中为是，那么将curLength赋值为其中的最大值

原理

对于 “xxxbcbxxxxa” (x 是随机的字符) 来说，我们现在处理最后一个字符 a。目前最长回文是bcb，长度是 3

如果 xxxxa 是回文，那么我们可以计算得到一个新的最大回文长度 5
如果 xxxa 是回文，那么我们可以计算得到一个新的最大回文长度 4
无需计算更短的字符串，因为其回文的最大长度不会大于现在回文长度
不用计算 xxxxxa，因为如果它是回文，那么去掉头和尾，xxxx仍然是回文，其长度是4，与假设矛盾。

代码

private byte[] sByte;

public String alongestPalindrome(String s) {
    int currLength = 0, start = 0, end = 0;
    sByte = s.getBytes();
    for(int i=0;i<s.length();i++){
        if(isPalindrome(i-currLength-1,i)){
            start = i-currLength-1;
            currLength = currLength+2;
        } else if(isPalindrome(i-currLength,i)){
            start = i-currLength;
            end = i+1;
            currLength = currLength+1;
        }
    }
    return s.substring(start, end);
}

public boolean isPalindrome( int begin, int end){
    if(begin<0) return false;
    while(begin<end){
        if(sByte[begin++]!=sByte[end--]) return false;
    }
    return true;
}