题目简介：
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
1
2
3
| 输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
|
示例 2：
思路：
定义一个dp[i][j]数组，来判断s[i]……s[j]的子字符串是否为回文串。
遍历字符串，若s[i] == s[j]，则存在以下两种情况都可判别s[i]……s[j]为回文串：
dp[i + 1][j - 1] == truej - i <= 2，这种情况说明i和j之间最多存在一个字符，若s[i] == s[j]，则s[i]……s[j]自然为回文串了
然后每次保存最长的子回文串，最后返回即可。
tip:
- 遍历时，需要以字符串结尾为开始(即结尾为最外层的循环，字符串开始的位置从
0依次增加到结尾的位置)，这样子才能保证判断dp[i + 1][j - 1]时不出错。
- 需要注意
substr()的使用方法。
代码如下：
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
| class Solution {
public:
string longestPalindrome(string s) {
vector<vector<bool>> dp(s.length(), vector<bool>(s.length()));
if(s.size() == 0)
return "";
int max_length = 0;
string res = "";
res += s[0];
for(int j = 1; j < s.length(); j++){
for(int i = 0; i <= j; i++){
if(s[i] == s[j] && (j - i <= 2 || dp[i + 1][j - 1])){
dp[i][j] = true;
if(j - i + 1 > max_length){
max_length = j - i + 1;
res = s.substr(i, j - i + 1);
}
}
}
}
return res;
}
};
|
