leetcode5.Longest Palindromic Substring

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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.

Example:

    Input: "cbbd"
    
    Output: "bb"

翻译过来就是说：在一个字符串中寻找最长的子字符串，该字符串是回数（即从左往右和从右往左读的结果是相同的）。该字符串的最大长度为1000

思路一：头指针+尾指针

遍历字符串，找到当前头指针的元素下一次出现时的下标，并且判断该子字符串是否是回数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public String longestPalindrome(String s) {
    StringBuilder result = new StringBuilder();
    int resultLength = 0;
    
    StringBuilder temp = new StringBuilder();
    for(int i = 0 ; i<s.length()-resultLength ; i++){
        
        for(int j = s.lastIndexOf(s.charAt(i)) ; j>=i+resultLength ; j = s.substring(0, j).lastIndexOf(s.charAt(i))){
            temp = new StringBuilder(s.substring(i, j+1));
            if(temp.toString().equals(temp.reverse().toString())){
                result = temp;
                resultLength = temp.length();
                break;
            }    
        }
    }
    return result.toString();
}

在该方法中，已经对遍历进行了优化，尽可能减少了无效遍历，例如当长度一定小于当前结果的最大长度时，跳出当前循环并进入下一个遍历。但是仍然有很多无效的遍历，因此该答案最后还是超时的。

思路二：指针+最大长度

现在我们从回数的特点入手。
假若一个字符串是一个回数，那么该字符串内部一定还存在更多的回数。例如，abbbcbbba是一个回数，那么bbbcbbb一定是一个回数，那么bcb也是回数，最后到b。同理，bccb是一个回数，那么cc也是一个回数。因此可以看出，假设当前一个字符串是回数，那么加上两侧的字符可能还是回数。假设当前一个字符串不是回数，那么加上右侧的字符可能构成一个回数。
因此，假设当前得到的回数的最大长度为n，我们可以判断n+1或者n+2是不是回数。
为什么这么判断呢？下面给出证明。
我们假设有一个字符串xxxxxxxxabaxxxxxxs，其中x代表任意字符。
假设此时指针指向s，而已知最大回数子字符串的长度为3。我们只需要判断xxxs以及xxxxs是不是回数。无需判断xxs乃至更近是因为它们的长度必然无法超过当前的最大长度。而无需判断xxxxxs乃至更远是因为假如xxxxxs是回数，那么xxxx一定是回数，则当前的最大长度为4而不是3，与题设不符。所以只需判断两种情况。
这里就充分利用了回数的性质，省去了很多无效的遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public String longestPalindrome2(String s) {
    StringBuilder result = new StringBuilder();
    int curLength = 0;
    
    for(int i = 0 ; i<s.length() ; i++){
        if(isPalindromic(s, i-curLength-1, i)){
            result = new StringBuilder(s.substring(i-curLength-1, i+1));
            curLength += 2;
        }else if(isPalindromic(s, i-curLength, i)){
            result = new StringBuilder(s.substring(i-curLength, i+1));
            curLength += 1;
        }
    }
    return result.toString();
}
public boolean isPalindromic(String s, int start, int end){
    if(start<0){
        return false;
    }
    while(start<end){
        if(s.charAt(start++)!=s.charAt(end--)) return false; 
    }
    return true;
}

思路三：由中间至两边找回数

思路三就像是思路一的彻底反转。思路一优先寻找回数的边缘，而思路三则直接从中间开始寻找，直至找到最远的边缘。
正如上面所说，回数的中间可能是一个单值，如aba中的b；也可能是双值，如abba中的bb。
我们可以对当前下标上的单值双值都进行尝试
以下是我在leetcode上找到的一个实现（88%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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;
    }
}}