Sui Xin's Blog

[LeetCode]5. 最长回文子串（Longest Palindromic Substring）

Posted on In Disqus:

题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。

示例 2：

输入: “cbbd”
输出: “bb”

解题思路

  • 方法一：以每个字母为回文中心，考虑回文长度为奇数和偶数两种情况，将子串向两边扩展；
  • 方法二：动态规划。令dp[j][i]为字符串从索引j到i是否为回文，则dp[j][i]依赖于dp[j + 1][i - 1]是否为回文和s[j]是否等于s[i]。

代码

方法一

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def longestPalindrome(self, s: str) -> str:
        length = len(s)
        left, right = 0, 0
        for i in range(length):
            if 2 * (length - i - 1) + 1 < right - left + 1:
                break
            l = r = i
            while l >= 0 and r < length and s[l] == s[r]:
                l -= 1
                r += 1
            if r - l - 2 >= right - left:
                left, right = l + 1, r - 1
            l, r = i, i + 1
            while l >= 0 and r < length and s[l] == s[r]:
                l -= 1
                r += 1
            if r - l - 2 >= right - left:
                left, right = l + 1, r - 1
        return s[left:right + 1]

执行用时 : 480 ms
内存消耗 : 13.2 MB

方法二：动态规划

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n));
        int max_len = 0;
        string out_s = "";
        for (int j = 0; j < n; j++) {
            for (int i = j; i >= 0; i--) {
                if (s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = 1;
                    if (j - i + 1 > max_len) {
                        max_len = j - i + 1;
                        out_s = s.substr(i, max_len);
                    }
                }
            }
        }
        return out_s;
    }
};

执行用时：296 ms
内存消耗：376.6 MB

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def longestPalindrome(self, s: str) -> str:
        length = len(s)
        dp = [[False] * length for _ in range(length)]
        res = ''
        max_length = -1
        for i in range(length):
            for j in range(i, -1, -1):
                if s[i] == s[j] and (i - j < 2 or dp[i - 1][j + 1]):
                    dp[i][j] = True
                    if i - j + 1 > max_length:
                        max_length = i - j + 1
                        res = s[j:i + 1]
        return res

执行用时 : 2956 ms
内存消耗 : 21.1 MB

参考

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

Related Posts