leetcode 05 最长子回文串 题解

发表于 | 更新于

题目

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

Example 1:

1
2
3
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

1
2
Input: "cbbd"
Output: "bb"

解法一

首先想到的当然是暴力解法了，对字符串的每一子字符串都进行是否为回文字符串的判定。所谓回文字符串就是正反都一样的字符串。

解法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool isPalindrome(string s){
    for(int i = 0; i < s.length() / 2; i++){
        if(s[i] != s[s.length() - 1 - i]){
            return false;
        }
    }
    return true;
}
string longestPalindrome(string s) {
    int maxlength = 1;
    string longeststr = s.substr(0, 1);
    for(int i = 0; i < s.length(); i++){
        if(maxlength >= s.length() - i) return longeststr;
        for(int j = maxlength + 1; j <= s.length() - i; j++){
            if(isPalindrome(s.substr(i, j))){
                if(j > maxlength){
                    longeststr = s.substr(i, j);
                    maxlength = j;
                }
            }
        }
    }
    return longeststr;
}

这里也对暴力解法进行了一些优化，比如在外层循环时，如果已经得到的最长回文字符串的长度大于此时要处理的子字符串的长度就直接返回；内存循环直接从此时得到的最长回文字符串的长度+1开始。然而，可以想见的是，效果依然是很差的。

解法二

之后思考许久也没有找到更好的算法，遂查看leetcode的提示，提示是说在寻找新的更长的回文字符串时，要用到已计算的回文字符串。这样一来可以减少判断回文字符串的时间。

解法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
string longestPalindrome(string s) {
    int minstart = 0, maxlength = 1;
    for(int i = 0; i < s.size(); i++){
        int sub = i, add = i;
        while(add < s.size() - 1 && s[add + 1] == s[add]){
            add++;
        }
        while(sub > 0 && add < s.size() - 1 && s[add + 1] == s[sub - 1]){
            add++;
            sub--;
        }
        int newlength = add - sub + 1;
        if(newlength > maxlength){
            minstart = sub;
            maxlength = newlength;
        }
    }
    return s.substr(minstart, maxlength);
}

这个解法是每次以循环位置i为中心，向两端扩展找到最长的回文字符串，在判断是否为回文字符串时，实际上只用判断s[add + 1] == s[sub - 1]，也就是这一步时间复杂度仅为O(1)，这样就大幅缩短了算法运行的时间。