[leetcode] Longest Palindromic Substring|找string中最长的中心对称substring

Posted by: lexigrey on: July 22, 2013

• In: leetcode
• 1 Comment

题目：给一个string，找这个str里面最长的中心对称substring

这个题上来就想一维dp，然后挣扎半天做不出来（找不到一维的d[i]和d[i + 1]的直接关系）。然后上网查答案，原来用二维dp做，而且速度是O(n^2)。其实这题上来就应该先想暴力，然后知道暴力的速度是n^3，然后想办法降一维，别上来就强迫自己O(n)！

二维dp:

1. d[i][j]是个boolean，表示(i, j)这个substring是不是中心对称。
2. d[i][j]
   • 正常情况下，d[i][j] = true when 1.A[i]==A[j] 2. d[i + 1][j – 1] == true (中间那部分已经中心对称了)
   • 处理i+1, j-1出界和左边反而大于右边的情况：
     • 当i == j时，d[i][j] = 1（一个字母肯定是中心对称）
     • 当i == j – 1时，说明两个字符是连着的，看A[i]是否==A[j]就行
3. 这个题的坑爹之处在于正常i从0~last, j从0~last那么循环不行。因为d[i][j]用到了d[i + 1][j – 1]，说明i要从后往前，j则要从前往后。导致二层循环是这种顺序：
   for (int i = last; i >= 0; i–)
   for(int j = i; j  <= last; j++)
   因为这事想了半天，有点焦躁。

不用二维数组的算法（直接按中心对称的定义来，而不是每个pair算一遍，可以省一维空间）：

1. 以每个元素以及间隔为中心（共2 * n – 1个），以相同的速度往两侧扩张，直到两边儿的值不相等了，说明palindrome在此打破，于是输出。这样每次输出的肯定是以当前这个点为中心最长的palindrome）
2. 这样过一遍数组，最长的就出来了。

public String longestPalindrome(String s) {
    String res = "";
    for (int i = 0; i < s.length(); i++) {
        String odd = expand(s, i, i);
        String even = expand(s, i, i + 1);
        String longer = odd.length() > even.length() ? odd : even;
        res = longer.length() > res.length() ? longer : res;
    }
    return res;
}
private String expand(String s, int i, int j) {
    while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
       i--;
       j++;
    }
    return s.substring(i + 1, j);
}

Tags: 2WayDP, palindrome, string