心之所向便是光

Leetcode 5.最长回文子串

  • 2021-05-22
  • 作者 Ender
  • 4.90K 字
  • 次阅读

题目描述：

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

示例 1：

1
2
3
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

1
2
输入：s = "cbbd"
输出："bb"

示例 3：

1
2
输入：s = "a"
输出："a"

示例 4：

1
2
输入：s = "ac"
输出："a"

提示：

  • $1 <= s.length <= 1000$
  • s 仅由数字和英文字母（大写和/或小写）组成

链接：

https://leetcode-cn.com/problems/longest-palindromic-substring

题目分析

1.暴力遍历解法

  最容易想到的解法，就是分割每一个子串，并用函数判断这个子串是否是回文串，如果是则更新到结果中。对所有的子串进行判断会超时，我们可以进行稍微的改进，也就是只从比当前结果长的子串开始判断，因为比当前结果短的子串即使是回文串也不会是答案，这样可以节省大量的时间。

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
class Solution {
public:
    bool isPalindromic(const string& s, int left, int right){
        while(left < right){
            if(s[left] != s[right]) return false;
            left++;
            right--;
        }
        return true;
    }

    string longestPalindrome(string s) {
        int maxlength = 1, begin = 0;
        for(int left = 0; left < s.size(); left++){
            // 从比当前结果更长的子串进行判断
            for(int right = left + maxlength; right < s.size(); right++){
                // 如果该子串是回文串则进行记录
                if(isPalindromic(s, left, right)){
                    maxlength = right - left + 1;
                    begin = left;
                }
            }
        }
        return s.substr(begin, maxlength);
    }
};

  时间复杂度：$O(n^3)$，其中 $n$ 是字符串的长度。因为我们一共需要判断 $O(n^2)$ 个数的子串，而每个子串判断时间是 $O(n)$。
  空间复杂度：$O(1)$。进行判断时并没有真的分割出子串，只是对下标进行记录，一共需要常数个变量进行记录。

2.动态规划解法

  对于某一个子串，只需要满足它的首尾去掉是一个回文串，而首尾本身也是相同的字符，那么它也是一个回文串。也即有dp[left, right] = dp[left+1][right-1] && s[left]==s[right]。其中 dp[left][right] 记录了由 s[left] 到 s[right] 的子串是一个回文串。需要注意的是，动态规划的转移方程是从短的子串向长的子串转移，则我们应该从短的字符串向长的字符串进行循环。而对于边界条件，子串字符个数为 1 时一定是一个回文串；子串字符个数为 2 时，两个字符相同时是一个回文串。

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
class Solution {
public:
    string longestPalindrome(string s) {
        if(s.size() < 2) return s;

        int maxlength = 1, begin = 0;
        vector<vector<bool>> dp(s.size(), vector<bool>(s.size()));

        // 对于所有单个字符标记为回文串（true）
        for(int i = 0; i < s.size(); i++){
            dp[i][i] = true;
        }
        // 从长度 2 开始循环
        for(int length = 2; length <= s.size(); length++){
            for(int left = 0; left + length <= s.size(); left++){
                int right = left + length - 1;

                // 首尾字符不相同
                if(s[left] != s[right]){
                    dp[left][right] = false;
                }
                // 首尾字符相同
                else{
                    // 长度为 2
                    if(right - left == 1){
                        dp[left][right] = true;
                    }
                    // 长度大于 2
                    else{
                        dp[left][right] = dp[left+1][right-1];
                    }
                }
                
                // 若长度超过当前最大长度则进行记录
                if(dp[left][right] && length > maxlength){
                    maxlength = length;
                    begin = left;
                }
            }
        }
        return s.substr(begin, maxlength);
    }
};

  时间复杂度：$O(n^2)$，其中 $n$ 是字符串的长度。因为动态规划的状态总数是 $O(n^2)$ ，而状态转移时间是 $O(1)$。
  空间复杂度：$O(n^2)$，其中 $n$ 是字符串的长度。即存储动态规划状态所需要的空间。

3.中心扩展解法

  类似于动态规划方法的状态转移思路，我们可以从某一个中心出发，向字符串两端不断扩展匹配是否是相同字符，这样可以得到某一个位置为中心时最大的回文子串长度，若比当前记录的长度更长则进行记录即可，反过来说，其实动态规划的边界情况也就是中心扩展解法的“回文中心”。而每次选择回文中心，有一个字符或者是两个字符的情况，我们要对其分别进行扩展。
  注意到我们进行扩展的子函数中循环是首先有对 s[left] 和 s[right] 是否相同进行判断的，这样字符个数为 1 时一定相同，而字符个数为 2 时是否相同也同时进行了判断，因此不必再单独判断字符为 2 时的边界情况。

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
class Solution {
public:
    pair<int, int> expandAroundCenter(const string& s, int left, int right) {
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            left--;
            right++;
        }
        return {left + 1, right - 1};
    }

    string longestPalindrome(string s) {
        int begin = 0, end = 0;
        for (int i = 0; i < s.size(); ++i) {
            auto [left1, right1] = expandAroundCenter(s, i, i);
            auto [left2, right2] = expandAroundCenter(s, i, i + 1);
            if (right1 - left1 > end - begin) {
                begin = left1;
                end = right1;
            }
            if (right2 - left2 > end - begin) {
                begin = left2;
                end = right2;
            }
        }
        return s.substr(begin, end - begin + 1);
    }
};

  时间复杂度：$O(n^2)$，其中 $n$ 是字符串的长度。我们一共需要扩展 $n$ 个长度为 1 的回文中心和 $n-1$ 个长度为 2 的回文中心，而对于每次扩展，最大长度为 $n/2$。因此总的时间复杂度为 $O((n+n-1)*n/2)=O(n^2)$。
  空间复杂度：$O(1)$。进行扩展时只需要进行判断并记录，一共需要常数个变量进行记录。

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
,
最后编辑：2021-06-09