Lexi's Leetcode solutions

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

Posted on: July 22, 2013

题目:给一个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);
}
Advertisements

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

用extend string的话,space的complexity就是O(N)了吧

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: