题干
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-palindromic-substring/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
1
2
3
4
5
6
7
8
9
10
| 示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
|
1
2
3
4
| 提示：
1 <= s.length <= 1000
s 仅由数字和英文字母组成
|
思路
考虑动态规划：一个字符串是回文串，那么可以从每个位置往两端扩展。枚举位置和长度。
官方思路学习: https://leetcode.cn/problems/longest-palindromic-substring/solutions/255195/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/
AC 代码
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) {
int len = s.length();
if(len < 2){
return s;
}
vector<vector<int>> dp(len,vector<int>(len));
int maxlen = 1,begin = 0;
for(int i = 0; i < len; i ++){
dp[i][i] = true;
}
int j;
for(int L = 2; L <= len; L ++){
for(int i = 0; i < len; i++){
j = i + L - 1;
if(j >= len){
break;
}
if(s[i] != s[j]){
dp[i][j] = false;
}else{
if(j-i < 3){
dp[i][j] = true;
}else{
dp[i][j] = dp[i+1][j-1];
}
}
if(dp[i][j] && j - i + 1 > maxlen){
maxlen = j - i + 1;
begin = i;
}
}
}
return s.substr(begin, maxlen);
}
};
|