标签：string 10.31 示例 int res 算法 字符串 回文
最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
string res="";
vector<vector<bool>> dp(n,vector<bool>(n,false));
for(int len=1;len<=n;len++){
for(int i=0;i+len-1<n;i++){
int j = i + len -1;
if(len==1){
dp[i][j] = true;
}
else if(len==2){
dp[i][j] = (s[i]==s[j]);
}
else{
dp[i][j] = dp[i+1][j-1] && (s[i]==s[j]);
}
if(dp[i][j] && len>res.size()){
res = s.substr(i,len);
}
}
}
return res;
}
};
关键：用动态规划的方法考虑，分解为如下几步
a.长度1-n的回文串，起始位置和结束位置考虑
b.长度n是长度n-1+首尾两字符考虑
c.初始情况1、2字符考虑
标签：string,
10.31,
示例,
int,
res,
算法,
字符串,
回文
From： https://www.cnblogs.com/minipython-wldx/p/17799925.html