[LeetCode]5. 最长回文子串(Longest Palindromic Substring)

题目描述

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

示例 1:

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

示例 2:

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

解题思路

  • 方法一:以每个字母为回文中心,考虑回文长度为奇数和偶数两种情况,将子串向两边扩展;
  • 方法二:动态规划。令dp[j][i]为字符串从索引ji是否为回文,则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