最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = “babad”

输出：”bab”

解释：”aba” 同样是符合题意的答案。

示例 2：

输入：s = “cbbd”

输出：”bb”

示例 3：

输入：s = “a”

输出：”a”

示例 4：

输入：s = “ac”

输出：”a”

提示：

1 <= s.length <= 1000

s 仅由数字和英文字母（大写和/或小写）组成

Solution

方法一

比较容易理解的一种方法。依次判断长度为s.length()~1的字符串是否为回文字符串，是就返回。

leetcode上该方法在测试中会超时。

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
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <string>

using namespace std;

class Solution {
public:
    bool isPalindrome(string &s) {
        int length = s.length();
        if (length == 0) {
            return false;
        }
        for (int i = 0; i < length / 2; ++i) {
            if (s[i] != s[length - 1 - i]) {
                return false;
            }
        }
        return true;
    }

    string longestPalindrome(string s) {
        int length = s.length();
        for (int i = 0; i < length; i++) {
            for (int j = 0; j <= i; j++) {
                string str = s.substr(j, length - i);
                if (isPalindrome(str)) {
                    return str;
                }
            }
        }
        return s.substr(0, 1);
    }
};

int main() {
    string s = "abaccccbaa";
    std::cout << Solution().longestPalindrome(s);
}

方法二

速度更快

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.size();
        if (len == 0|| len == 1)
            return s;
        int start = 0; //回文串起始位置
        int max = 1; //回文串最大长度
        vector<vector<int>> dp(len,vector<int>(len));//定义二维动态数组
        for (int i = 0; i < len; i++)//初始化状态
        {
            dp[i][i] = 1;
            if (i < len-1 && s[i] == s[i+1])
            {
                dp[i][i + 1] = 1;
                max = 2;
                start = i;
            }
        }
        for (int l = 3; l <= len; l++)//l表示检索的子串长度，等于3表示先检索长度为3的子串
        {
            for (int i = 0; i + l - 1 < len; i++)
            {
                int j = l + i - 1;//终止字符位置
                if (s[i] == s[j] && dp[i + 1][j - 1] == 1) //状态转移
                {
                    dp[i][j] = 1;
                    start = i;
                    max = l;
                }
            }
        }
        return s.substr(start,max);//获取最长回文子串
    }
};

int main() {
    string s = "kztakrekvefgchersuoiuatzlmwynzjhdqqftjcqmntoyckqfawikkdrnfgbwtdpbkymvwoumurjdzygyzsbmwzpcxcdmmpwzmeibligwiiqbecxwyxigikoewwrczkanwwqukszsbjukzumzladrvjefpegyicsgctdvldetuegxwihdtitqrdmygdrsweahfrepdcudvyvrggbkthztxwicyzazjyeztytwiyybqdsczozvtegodacdokczfmwqfmyuixbeeqluqcqwxpyrkpfcdosttzooykpvdykfxulttvvwnzftndvhsvpgrgdzsvfxdtzztdiswgwxzvbpsjlizlfrlgvlnwbjwbujafjaedivvgnbgwcdbzbdbprqrflfhahsvlcekeyqueyxjfetkxpapbeejoxwxlgepmxzowldsmqllpzeymakcshfzkvyykwljeltutdmrhxcbzizihzinywggzjctzasvefcxmhnusdvlderconvaisaetcdldeveeemhugipfzbhrwidcjpfrumshbdofchpgcsbkvaexfmenpsuodatxjavoszcitjewflejjmsuvyuyrkumednsfkbgvbqxfphfqeqozcnabmtedffvzwbgbzbfydiyaevoqtfmzxaujdydtjftapkpdhnbmrylcibzuqqynvnsihmyxdcrfftkuoymzoxpnashaderlosnkxbhamkkxfhwjsyehkmblhppbyspmcwuoguptliashefdklokjpggfiixozsrlwmeksmzdcvipgkwxwynzsvxnqtchgwwadqybkguscfyrbyxudzrxacoplmcqcsmkraimfwbauvytkxdnglwfuvehpxd";
    
    std::cout << Solution().longestPalindrome(s);
}