https://leetcode.com/problems/longest-palindromic-substring/题目描述
Given a string?s, return?the longest palindromic substring?in?s.
Example 1:
Input: s = "babad" Output: "bab" Explanation: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd" Output: "bb"
Constraints:
1 <= s.length <= 1000s?consist of only digits and English letters.
解题思路
【C++解法】
1. 动态规划
dp[i][j]表示为s[i,j]是否为回文串；注意单字符一定为回文串，那么dp表格的对角线就可以预先填上
当s长度小于等于2时，s是否为回文串，只需要判断s[i]和s[j]是否相等
当s长度大于2时，沿 ↗ 方向，即判断s[i][j]是否为回文，就只要判断内部为回文串即两端是否相等
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
vector< vector<int>> dp(n, vector<int>(n,0));
int start = 0, maxLen= 0;
for(int i=0; i<n; i++) {
for(int j=0; j<=i; j++) {
if(s[i]==s[j] && (i-j<3 || dp[i-1][j+1])) {
dp[i][j] = 1;
}
int len = i-j+1;
if(len>=maxLen && dp[i][j]) {
maxLen = len ;
start = j;
}
}
}
return s.substr(start, maxLen);
}
};或者，遍历长度
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
vector< vector<int>> dp(n, vector<int>(n,0));
int start = 0, maxLen = 1;
for (int i=0; i<n; i++) {
dp[i][i]=1;
if ((i<n-1) && (s[i]==s[i+1])) {
dp[i][i+1]=1;
start = i;
maxLen=2; //初始化时注意当前最长回文子串长度；
}
}
for (int L=3; L<=n; L++) {//枚举子串长度
for (int i=0; i+L-1<n; i++) {//枚举子串起始端点
int j=i+L-1;//子串右端点
if (s[i]==s[j] && dp[i+1][j-1]==1) {
dp[i][j] = 1;
maxLen = L;//更新最长回文子串长度;
start = i;
}
}
}
return s.substr(start, maxLen);
}
};2.?中心扩展
参考文献