5.最长回文子串“
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
思路
基本思想
与
647题
思路一致，只是统计的目标不一样，647题统计的是所有回文子串的数量，本题统计的是所有回文子串中最长的回文子串，需要多一步，最初的想法是使用回溯法将字符串的所有分割结果穷举出来，然后判断每一个子串是否是回文子串，然后判断当前回文子串是否变长，变长的回文子串就会更新，经历三步：
- 穷举字符串的所有分割结果
- 判断字符串是不是回文子串
- 最长回文子串是否需要更新
但是此方法超时，主要问题还是在回溯法穷举的时间太长，并且长回文子串一定包含短回文子串，也就是重复判断了很多次，短的回文子串的判断结果可以交给长的回文子串，于是想到了动态规划
当i+1~j-1范围内的子串是回文串时，加上s[i]==s[j]的条件，回文串的长度就会进一步变大，并且i+1~j-1到i~j范围内的变化是从左下角到右上角，所以需要从左下角开始统计，然后将左下角的结果用到右上角上
dp数组的含义是：dp[i][j]代表i~j范围内的子串是否是回文子串
此题中没有递推公式，只要当i+1~j-1范围内的子串是回文串时，加上s[i]==s[j]的条件就可以形成新的回文串
只要有新的回文串，最长回文串的结果就有可能更新
要清楚遍历字符串时,每一行中的遍历范围是从对角线向前的元素,这样从左下角向右上角统计的过程中字符串的遍历范围逐步扩大,最终遍历整个字符串,得到最长的回文子串
执行流程
- 初始化dp数组，默认所有范围内的子串都不是回文串
- 从左下角开始向右上角推导，满足一定条件说明当前范围内的子串是回文子串
- 判断最长回文子串是否需要更新
- 遍历完成之后，返回最终的结果
代码
根据以上分析，得出以下代码：
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
| class Solution {
public:
string res="";
string longestPalindrome(string s) {
//使用动态规划
string res="";
vector<vector<bool>> dp(s.size(),vector<bool>(s.size(),false));
//从右上角开始,从对角线向后统计
for(int i=s.size()-1;i>=0;--i){
for(int j=i;j<s.size();++j){
//当前两个位置的字符相等，看被夹住的部分是不是回文
if(s[i]==s[j]){
if(i==j||i+1==j){
dp[i][j]=true;
//当前回文串的长度大于最长回文串长度
//更新最长回文串
if((j-i+1)>res.size())
res=s.substr(i,j-i+1);
}else if(dp[i+1][j-1]){
dp[i][j]=true;
//当前回文串的长度大于最长回文串长度
//更新最长回文串
if((j-i+1)>res.size())
res=s.substr(i,j-i+1);
}
}
}
}
return res;
}
};
|
java代码为:
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 String longestPalindrome(String s) {
boolean[][] dp=new boolean[s.length()][s.length()];
String res="";
for(int i=s.length()-1;i>=0;--i){
for(int j=i;j<s.length();++j){
//遇到范围边界的两个字符相等
if(s.charAt(i)==s.charAt(j)){
if(i==j||i+1==j){
dp[i][j]=true;
if(j+1-i>res.length()){
res=s.substring(i,j+1);
}
}else if(dp[i+1][j-1]){
dp[i][j]=true;
if(j+1-i>res.length())
res=s.substring(i,j+1);
}
//尝试截取更长的回文子串
}
}
}
return res;
}
}
|
总结
长回文子串的判断过程包含了短回文子串的判断过程，也就是说短回文子串的判断结果可以给长回文子串一些参考，根据这个思想使用动态规划解题
需要注意的是,一旦当前回文子串的长度大于res,就可以更新res,当前回文子串的长度为j+1-i