LongestPalindromicSubstring [source code]

public class LongestPalindromicSubstring {
static
/******************************************************************************/
class Solution {
    public String longestPalindrome(String s) {
        char[] chs = s.toCharArray ();
        int max_len = 1, max_idx = 0;
        for (int i = 1; i < chs.length; i++) {
            int cur_ofs = palinOfs (chs, i, i), cur_len = 1 + 2 * cur_ofs, cur_ofs2 = 0, cur_len2 = 0;
            if (i - 1 >= 0 && chs[i - 1] == chs[i]) {
                cur_ofs2 = palinOfs (chs, i - 1, i);
                cur_len2 = 2 + 2 * cur_ofs2;
            }
            int cur_max_len = 0, cur_max_idx = 0;
            if (cur_len > cur_len2) {
                cur_max_len = cur_len;
                cur_max_idx = i - cur_ofs;
            } else {
                cur_max_len = cur_len2;
                cur_max_idx = i - 1 - cur_ofs2;
            }
            if (cur_max_len > max_len) {
                max_len = cur_max_len;
                max_idx = cur_max_idx;
            }
        }
        return s.substring (max_idx, max_idx + max_len);
    }

    int palinOfs (char[] chs, int i, int j) {
        assert i <= j;
        int res = 0;
        while (i - 1 >= 0 && j + 1 < chs.length && chs[i - 1] == chs[j + 1]) {
            i--;
            j++;
            res++;
        }
        return res;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        LongestPalindromicSubstring.Solution tester = new LongestPalindromicSubstring.Solution();
        String[] inputs = {
            "cbbd", "bb",
            "babad", "bab",
            "bb", "bb",
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            String s = inputs[2 * i], ans = inputs[2 * i + 1];
            System.out.println (Printer.separator ());
            String output = tester.longestPalindrome (s);
            System.out.printf ("%s -> %s, expected: %s\n", 
                s, Printer.wrapColor (output, output.equals (ans) ? "green" : "red"), ans
            );
        }
    }
}

不出意外应该是一个sliding window的题目, 直接写写看; 不对, 想了一下, 好像不是sliding window能够解决的, 因为这里验证的不是一个counts类型的信息;

啰嗦了半天, 最后好歹是AC了, 速度是22ms (62%).

感觉状态不太好, 很多边缘的数字写的太不仔细了;

不过还是一些经验的东西, 首先看我计算palin length的helper函数里面, 我的循环用的是pre leaf位置的判断, 我感觉这里这个比较方便; 我以前其实一直对pre位置的判断比较抵触, 我也不知道是什么原因; 事实用下来, 感觉pre的方式很多时候都是至少可以做到跟leaf位置判断一样好用, 而且有时候甚至能涵盖一些更特殊的情形;

palindrome: radiant expansion

这个好像是之前见过一次了, palindrome题目好像经常的做法就是这样, 对于一个index开始, 然后两头发散;

另外, 在计算的时候, 要注意palindrome的长度为奇偶的时候, 中点的处理方式略有区别, 要注意都要检查一下;

另外, 我这里这个helper的设计, 我一开始以为是比较好的, 因为可以同时对应奇数长度palindrome的中点和偶数情形; 然后返回的是一个offset, 认为更有利于后面计算; 不过后面发现这个设计还是不够好, 把太多的复杂性留给了主函数. 事实上, 这个helper既然主要功能就是找palindrome, 我认为最好的结果就是直接返回一个interval就行了; 你可以用一个{start, length}这样的新class来表示; 当时其实也是图方便就没有做这个方法, 导致主函数里面最后写的就跟现在这样, 有点乱;

editorial

Approach #1 (Longest Common Substring) [Accepted]

这个方法没有给代码, 只给了一个思路, 基本就是, 先把S给reverse, 然后找到reverse之后的S(S')跟S之间的LCS. 但是这个方法有问题, 比如, abacdfgdcaba reverse之后得到了abacdfgdcaba, 他们的LCS并不是我们要的最长palindrome;

We could see that the longest common substring method fails when there exists a reversed copy of a non-palindromic substring in some other part of S. To rectify this, each time we find a longest common substring candidate, we check if the substring’s indices are the same as the reversed substring’s original indices. If it is, then we attempt to update the longest palindrome found so far; if not, we skip this and find the next candidate.

找到LCS之后, 还要再给他也reverse一下, 然后查index, 看是否相同. 这个就很麻烦了, 最后的复杂度是N^3, 不过这个方法还是给出了一个解决palindrome问题的新思路: LCS of reverse.

他这个作者认为这个方法是N^2, 我不太认同, 毕竟LCS本身就要N^2, 然后他后面对于找到的这个LCS的验证, 实际上也是要N的;

Approach #2 (Brute Force) [Time Limit Exceeded]

简单的, 找到所有的substring, 然后test是否palindrome; 这个的话, 就有N^3的复杂度;

Approach #3 (Dynamic Programming) [Accepted]

大概还是上面的做法, 不过用DP的方式来validate palindrome, 因为你validate的时候实际上是有很多overlapping的, 比如如果你知道bab的结果了, 你也就知道ababa的结果了. 这个优化总体来说还是很trivial的:

string longestPalindromeDP(string s) {  
  int n = s.length();  
  int longestBegin = 0;  
  int maxLen = 1;  
  bool table[1000][1000] = {false};  
  for (int i = 0; i < n; i++) {  
    table[i][i] = true;  
  }  
  for (int i = 0; i < n-1; i++) {  
    if (s[i] == s[i+1]) {  
      table[i][i+1] = true;  
      longestBegin = i;  
      maxLen = 2;  
    }  
  }  
  for (int len = 3; len <= n; len++) {  
    for (int i = 0; i < n-len+1; i++) {  
      int j = i+len-1;  
      if (s[i] == s[j] && table[i+1][j-1]) {  
        table[i][j] = true;  
        longestBegin = i;  
        maxLen = len;  
      }  
    }  
  }  
  return s.substr(longestBegin, maxLen);  
}

Approach #4 (Expand Around Center) [Accepted]

public String longestPalindrome(String s) {  
    int start = 0, end = 0;  
    for (int i = 0; i < s.length(); i++) {  
        int len1 = expandAroundCenter(s, i, i);  
        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;  
        }  
    }  
    return s.substring(start, end + 1);  
}  

private int expandAroundCenter(String s, int left, int right) {  
    int L = left, R = right;  
    while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {  
        L--;  
        R++;  
    }  
    return R - L - 1;  
}

基本跟我的思路是一样的;

Approach #5 (Manacher's Algorithm) [Accepted]

作者的原话是, 这个算法很麻烦, 所以一般如果你面试的时候被问到了这一题, 那么你只要能够想出上面expansion的方法就行了;

关于这个算法, 在这里: https://articles.leetcode.com/longest-palindromic-substring-part-ii/

首先, 当我们把substring search从N^2改进到N的KMP的时候, 是怎么得到启发的? 我们是通过研究WorstCase找到需要改进的地方的; 这里这个算法其实也是在上面N^2的算法的基础上, 思考WorstCase然后找到改进空间;

The worst case scenarios are the inputs with multiple palindromes overlapping each other. For example, the inputs: “aaaaaaaaa” and “cabcbabcbabcba”. In fact, we could take advantage of the palindrome’s symmetric property and avoid some of the unnecessary computations.

大概搜了一下, 这个算法好像是相当难的, geeks4geeks上面用4个part才把这个讲完;

我还是先看LeetCode给的这个文章;

T = # a # b # a # a # b # a #  
P = 0 1 0 3 0 1 6 1 0 3 0 1 0

这个是之前做median题的时候碰到过一次的技巧: 用隔板来统一解决奇偶性长度的问题;

// Transform S into T.  
// For example, S = "abba", T = "^#a#b#b#a#$".  
// ^ and $ signs are sentinels appended to each end to avoid bounds checking  
string preProcess(string s) {  
  int n = s.length();  
  if (n == 0) return "^$";  
  string ret = "^";  
  for (int i = 0; i < n; i++)  
    ret += "#" + s.substr(i, 1);  

  ret += "#$";  
  return ret;  
}  

string longestPalindrome(string s) {  
  string T = preProcess(s);  
  int n = T.length();  
  int *P = new int[n];  
  int C = 0, R = 0;  
  for (int i = 1; i < n-1; i++) {  
    int i_mirror = 2*C-i; // equals to i' = C - (i-C)  

    P[i] = (R > i) ? min(R-i, P[i_mirror]) : 0;  

    // Attempt to expand palindrome centered at i  
    while (T[i + 1 + P[i]] == T[i - 1 - P[i]])  
      P[i]++;  

    // If palindrome centered at i expand past R,  
    // adjust center based on expanded palindrome.  
    if (i + P[i] > R) {  
      C = i;  
      R = i + P[i];  
    }  
  }  

  // Find the maximum element in P.  
  int maxLen = 0;  
  int centerIndex = 0;  
  for (int i = 1; i < n-1; i++) {  
    if (P[i] > maxLen) {  
      maxLen = P[i];  
      centerIndex = i;  
    }  
  }  
  delete[] P;  

  return s.substr((centerIndex - 1 - maxLen)/2, maxLen);  
}

注意循环的范围, 忽略了两头的sentinel; 另外注意最后返回的时候, 因为我们最后返回结果照顾的应该是没有加隔断之前的数量, 所以最后有一点小的转换. 如果没把握, 自己笔算几个数字试试看就行了. 记住, 这种复杂的算法, 你假如说真的是面试的时候要写, 肯定旁边要始终放着一个例子, 比如一个T和P的实际的例子的, 不可能闭着眼睛写出来, 你真有这个本身面试官也不会信你;

看这个算法的时候, 记住index和length(offset)的区别, 以及index + offset = index.

算法本身是对的, 但是讲的很浅显, 基本就是把代码给翻译了一遍的感觉;

注意他这个while循环, 也是用的pre leaf判断;

整个代码本身看起来倒是蜜汁简单, 不过感觉还是没有牢固的掌握;

另外, 这个时间分析感觉很奇怪;

In each step, there are two possibilities. If P[ i ] ≤ R – i, we set P[ i ] to P[ i’ ] which takes exactly one step. Otherwise we attempt to change the palindrome’s center to i by expanding it starting at the right edge, R.

这里在上面这个代码可能看的还不太清楚, 看下一篇文章讲的更好;

Extending R (the inner while loop) takes at most a total of N steps, and positioning and testing each centers take a total of N steps too. Therefore, this algorithm guarantees to finish in at most 2*N steps, giving a linear time solution.

这个时间分析就有点奇怪了;

如果让我来分析这个时间的话, 我会考虑, 你看, 我们这个expansion的过程, 是一个non-decreasing的顺序进行的, 也就是我们一个iteration的expansion只会在之前的R的基础上进行, 而不是从0开始, 所以最后这个extension的过程, 只会占用N的时间, 这个是一个aggregate的角度分析; 第一个循环, 非expansion的部分, 是N, 然后最后一个pass, 是N, 所以我认为是3N;

另外一篇中文的讲这个算法的文章

这个算法看了三天，终于理解了，在这里记录一下自己的思路，免得以后忘了又要想很久- -.

首先用一个非常巧妙的方式，将所有可能的奇数/偶数长度的回文子串都转换成了奇数长度：在每个字符的两边都插入一个特殊的符号。比如 abba 变成 #a#b#b#a#， aba变成 #a#b#a#。为了进一步减少编码的复杂度，可以在字符串的开始加入另一个特殊字符，这样就不用特殊处理越界问题，比如$#a#b#a#（注意，下面的代码是用C语言写就，由于C语言规范还要求字符串末尾有一个'\0'所以正好OK，但其他语言可能会导致越界）。

下面以字符串12212321为例，经过上一步，变成了 S[] = "$#1#2#2#1#2#3#2#1#";

然后用一个数组 P[i] 来记录以字符S[i]为中心的最长回文子串向左/右扩张的长度（包括S[i]，也就是把该回文串“对折”以后的长度），比如S和P的对应关系：
S  #  1  #  2  #  2  #  1  #  2  #  3  #  2  #  1  #  
P  1  2  1  2  5  2  1  4  1  2  1  6  1  2  1  2  1
(p.s. 可以看出，P[i]-1正好是原字符串中回文串的总长度）

看最后总结, 这里的P的定义跟上面的稍微有点不同.

那么怎么计算P[i]呢？该算法增加两个辅助变量（其实一个就够了，两个更清晰）id和mx，其中 id 为已知的右边界最大的回文子串的中心，mx则为id+P[id]，也就是这个子串的右边界。

这里明确给出了R和C的定义, 而LeetCode的文章好像并没有明确指出;

然后可以得到一个非常神奇的结论，这个算法的关键点就在这里了：如果mx > i，那么P[i] >= MIN(P[2 * id - i], mx - i)。就是这个串卡了我非常久。实际上如果把它写得复杂一点，理解起来会简单很多：
//记j = 2 * id - i，也就是说 j 是 i 关于 id 的对称点(j = id - (i - id))  
if (mx - i > P[j])   
    P[i] = P[j];  
else  // P[j] >= mx - i   
    P[i] = mx - i; // P[i] >= mx - i，取最小值，之后再匹配更新。

这个解释的非常好, 一开始的写法的那个min实在是有点绕人, 不理解原理很难想通;

当然光看代码还是不够清晰，还是借助图来理解比较容易。

当 mx - i > P[j] 的时候，以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中，由于 i 和 j 对称，以S[i]为中心的回文子串必然包含在以S[id]为中心的回文子串中，所以必有 P[i] = P[j]，见下图。

[图片省略]

当 P[j] >= mx - i 的时候，以S[j]为中心的回文子串不一定完全包含于以S[id]为中心的回文子串中，但是基于对称性可知，下图中两个绿框所包围的部分是相同的，也就是说以S[i]为中心的回文子串，其向右至少会扩张到mx的位置，也就是说 P[i] >= mx - i。至于mx之后的部分是否对称，就只能老老实实去匹配了。

[图片省略]

对于 mx <= i 的情况，无法对 P[i]做更多的假设，只能P[i] = 1，然后再去匹配了。

于是代码如下：
//输入，并处理得到字符串s  
int p[1000], mx = 0, id = 0;  
memset(p, 0, sizeof(p));  
for (i = 1; s[i] != '\0'; i++) {  
    p[i] = mx > i ? min(p[2*id-i], mx-i) : 1;  
    while (s[i + p[i]] == s[i - p[i]]) p[i]++;  
    if (i + p[i] > mx) {  
        mx = i + p[i];  
        id = i;  
    }  
}  
//找出p[i]中最大的

注意他这个算法的P的定义跟上面LeetCode的那个写法的定义不同; 各有好处, 我感觉LeetCode那个好像好记一些; LeetCode那个的P里面记忆的是一个offset, 而这里的P记录的则要多+一个1, 是center本身的长度(或者他自己的说法, 对折之后的长度).

这个base改变之后, 大概的处理要稍微变动一下; 对应起来就行了; 他这个定义方法, 最后是有一个exclusive value的处理在里面的, 我不太喜欢这个, 我个人还是喜欢指哪打哪的直接的index来表达一个interval; 记住这个习惯, 熟悉这个习惯, 就行了, 不要去羡慕别人的做法;

比如因为他的这个定义方式, 他这里的expansion的过程看起来都有点不像是pre leaf判断, 实际上还是的;

geeks4geeks解法

这个有时间再看, 讲的非常非常的详细; 另外, 他们的P里面存的也是offset;

太长了, 实在是没时间看了;

discussion最优解:

public class Solution {  
private int lo, maxLen;  

public String longestPalindrome(String s) {  
    int len = s.length();  
    if (len < 2)  
        return s;  

    for (int i = 0; i < len-1; i++) {  
        extendPalindrome(s, i, i);  //assume odd length, try to extend Palindrome as possible  
        extendPalindrome(s, i, i+1); //assume even length.  
    }  
    return s.substring(lo, lo + maxLen);  
}  

private void extendPalindrome(String s, int j, int k) {  
    while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {  
        j--;  
        k++;  
    }  
    if (maxLen < k - j - 1) {  
        lo = j + 1;  
        maxLen = k - j - 1;  
    }  
}}

利用了一个global变量, 让很多事情简单很多: 不需要通过返回值来传递结果, 毕竟我们最后实际上关注的也就是一个最值而已;

底下的一个高票改写:

    public String longestPalindrome(String s) {  
        String max = "";  
        for (int i = 0; i < s.length(); i++) {  
            String s1 = extend(s, i, i), s2 = extend(s, i, i + 1);  
            if (s1.length() > max.length()) max = s1;  
            if (s2.length() > max.length()) max = s2;  
        }  
        return max;  
    }  

    private String extend(String s, int i, int j) {  
        for (; 0 <= i && j < s.length(); i--, j++) {  
            if (s.charAt(i) != s.charAt(j)) break;  
        }  
        return s.substring(i + 1, j);  
    }

但是我不喜欢这个解答, 因为他是把一个string作为返回值传来传去的, 这个在java里面是不聪明的, 在java里面表达sub概念的时候大部分时候都是用int index来表达更好一点; 他这个不停的返回string的操作是可能导致很大的cost的;

一个小的优化:

@peter4k said in Very simple clean java solution:

We can improve the solution by checking if the current center could expand to a palindrome that is longer than the current palindrome:

First we find a string with the current center and the length longer than the current length

Check the start and the end of this string are the same

If not, return

Here is an example:
If we have a string abcbebss, and we are now at the center e.

From previous iterations we already know that the longest length is 3 (bcb)

we find the string with length larger than 3 (in this case it is a even string, so length of 5), and center as e: cbebs

we check if the start and end are the same. If not return

Here is the solution:

public class Solution {  
private int lo, maxLen, half, len;  

public String longestPalindrome(String s) {  
  len = s.length();  
  if (len < 2)  
    return s;  

    for (int i = 0; i < len-1; i++) {  
      extendPalindrome(s, i, i);  //assume odd length, try to extend Palindrome as possible  
      extendPalindrome(s, i, i+1); //assume even length.  
    }  
    return s.substring(lo, lo + maxLen);  
}  

private void extendPalindrome(String s, int j, int k) {  
        //check the start and the end of the string with length longer than maxLen  
        if(j - half < 0 || k + half >= len || s.charAt(j - half) != s.charAt(k + half)) return;   

  while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {  
    j--;  
    k++;  
  }  
  if (maxLen < k - j - 1) {  
    lo = j + 1;  
    maxLen = k - j - 1;  
    half = maxLen / 2;  
  }  
}}

想法还是挺有意思的;

string longestPalindrome(string s) {  
    if (s.empty()) return "";  
    if (s.size() == 1) return s;  
    int min_start = 0, max_len = 1;  
    for (int i = 0; i < s.size();) {  
      if (s.size() - i <= max_len / 2) break;  
      int j = i, k = i;  
      while (k < s.size()-1 && s[k+1] == s[k]) ++k; // Skip duplicate characters.  
      i = k+1;  
      while (k < s.size()-1 && j > 0 && s[k + 1] == s[j - 1]) { ++k; --j; } // Expand.  
      int new_len = k - j + 1;  
      if (new_len > max_len) { min_start = j; max_len = new_len; }  
    }  
    return s.substr(min_start, max_len);  
}

咋一看, 这个思路很无聊, 为什么要skip duplicate, 直接让后面的iteration来自动处理不行吗; 但是仔细思考了一下, 他这里实际上是有非常深刻的insight的;

在你自己写的时候, 一个很明显的问题, 是你要考虑当你expand的时候, 你的center是一个字母还是两个字母: 对应的你就有两种不同的expand方法; 这里这个人的这个优化实际上是把这个观点带的更进了一步: 假如你进入了一个aaaaa这样的duplicate run, 一个关键的信息是, 这样一个run只可能位于一个longest palindrome里面, 所以假如我们从当中的任何一个位置expand过了, 那么就永远不用从其他的later的位置重新expand, 这个也就是这个算法的核心思路;

每当碰到一个duplicate run, 直接先把i给advance到这个run的后面, 这样i就相当于跳过了很多的内容; 其他的部分应该不难理解了;

一个改写:

string longestPalindrome(string s) {  
    int len = s.size();  
    if (len <= 1) return s;  
    int lpos = 0, lm = 0; // position of first letter and length  
    for ( int i = 0; i < len - 1; i++) {  
        if (lm >= (len - i) * 2) return s.substr(lpos,lm);  
        int count = 0;  
        while (s[i + 1] == s[i] && i++ < len - 1)   
             count++;  
        int end = i;  
        int first = i - count;  
        while (s[--first] == s[++end] && first >= 0 && end < len);  
        end--;  
        first++;  
        if ( lm < end - first + 1){  
            lpos = first;  
            lm = end - first + 1;  
        }  
    }  
    return s.substr(lpos, lm);  
}

他说是加速了, 不过我也没看出来到底有什么改进的地方, 感觉实际上是差不多的;

@liji94188 said in (AC) relatively short and very clear Java solution:

Key idea, every time we move to right, we only need to consider whether using this new character as tail could produce new palindrome string of length (current length +1) or (current length +2)

    public class Solution {  
        public String longestPalindrome(String s) {  
            String res = "";  
            int currLength = 0;  
            for(int i=0;i<s.length();i++){  
                if(isPalindrome(s,i-currLength-1,i)){  
                    res = s.substring(i-currLength-1,i+1);  
                    currLength = currLength+2;  
                }  
                else if(isPalindrome(s,i-currLength,i)){  
                    res = s.substring(i-currLength,i+1);  
                    currLength = currLength+1;  
                }  
            }  
            return res;  
        }  

        public boolean isPalindrome(String s, int begin, int end){  
            if(begin<0) return false;  
            while(begin<end){  
              if(s.charAt(begin++)!=s.charAt(end--)) return false;  
            }  
            return true;  
        }  
    }

For friends who are confused about the key idea to check only new palindrome with length = current length +2 or +1, I add some more explanation here.

Example: "xxxbcbxxxxxa", (x is random character, not all x are equal) now we   
          are dealing with the last character 'a'. The current longest palindrome  
          is "bcb" with length 3.  
1. check "xxxxa" so if it is palindrome we could get a new palindrome of length 5.  
2. check "xxxa" so if it is palindrome we could get a new palindrome of length 4.  
3. do NOT check "xxa" or any shorter string since the length of the new string is   
   no bigger than current longest length.  
4. do NOT check "xxxxxa" or any longer string because if "xxxxxa" is palindrome   
   then "xxxx" got  from cutting off the head and tail is also palindrom. It has   
   length > 3 which is impossible.'

这个算法刚开始一直没看懂, 不过upvote很高, 还是耐着性质看完了, 看懂了之后才理解, 他这个算法真的是相当聪明的; 具体的我也不好说, 自己看他下面那个例子的解释, 讲的非常的详细;

不过他对于substring的用法不是很讲究, 下面有人给出了优化:

    public String longestPalindrome(String s) {  
        int curLen = 0;  
        int start = -1;  
        char[] array = s.toCharArray();  
        for(int i = 0; i < array.length; i++) {  
            if(isPalindrome(array, i - curLen - 1, i)) {  
                start = i - curLen - 1;  
                curLen += 2;  
            } else if (isPalindrome(array, i - curLen, i)) {  
                start = i - curLen;  
                curLen += 1;  
            }  
        }  
        return new String(array, start, curLen);  
    }  
    private boolean isPalindrome(char[] array, int start, int end) {  
        if(start < 0) {  
            return false;  
        }  
        while(start < end) {  
            if(array[start++] != array[end--]) {  
                return false;  
            }  
        }  
        return true;  
    }

我验证了一下, 15(95), 一个N^2的解法能做到这个, 很不可思议了;

另外一个DP的解法:

public String longestPalindrome(String s) {  
    if(s == null || s.length() <= 1) {  
        return s;  
    }  
    int len = s.length();  
    int start = 0, end = 0;  
    // palindrome[i][j] : substring(i,j) is palindrome or not?  
    boolean[][] palindrome = new boolean[len][len];  
    // length = 1  
    for(int i=0;i<len;i++) {  
        palindrome[i][i] = true;  
    }  
    // length = 2  
    for(int i=1;i<len;i++) {  
        if(s.charAt(i-1) == s.charAt(i)) {  
            palindrome[i-1][i] = true;  
            start = i-1; end = i+1;  
        }  
    }  
    // length = k (k=2..len)  
    for(int k=2;k<len;k++) {  
        for(int i=0;i+k<len;i++) {  
            int j = i+k;  
            if(s.charAt(i) == s.charAt(j) && palindrome[i+1][j-1]) {  
                palindrome[i][j] = true;  
                start = i; end = j+1;  
            }  
        }  
    }  
    return s.substring(start, end);  
}

这个总体还是好理解的, again, 避免使用substring太多;

当然, 这个算法对于扩散思路确实没有什么优势, 不过多了解一个思路也是不错的; 毕竟palindrome这个话题, 本身就是一个对于DP Property暗示极强的: 典型的只要check一下root decision就行了, which takes only O(1).

submission最优解, Manacher: 10(99.7).

class Solution {  
    int len = 0, maxLength = 0, init = 0;  
    public String longestPalindrome(String s) {  
        char[] chars = s.toCharArray();  
        len = s.length();  
        if (len <= 1) return s;  
        for (int i = 0; i < len; i++) {  
            i = manacher(chars, i);  
        }  
        return s.substring(init, init + maxLength);  
    }  

    public int manacher(char[] chars, int k) {  
        int i = k - 1, j = k;  
        while (j < len - 1 && chars[j] == chars[j + 1]) j++;  
        int nextCenter = j++;  
        while (i >= 0 && j < len && chars[i] == chars[j]) {  
            i--;  
            j++;  
        }  
        if (j - i - 1 > maxLength) {  
            maxLength = j - i - 1;  
            init = i + 1;  
        }  
        return nextCenter;  
    }  
}

不对啊, 这个是Manacher吗? 这个是之前看到的那个c++的解法类似的解法啊? 为什么这个叫做Manacher? 感觉不是一回事吧. 很奇怪;

Problem Description

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"  

Output: "bab"  

Note: "aba" is also a valid answer.