LeetCode-5 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例 1：
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。
示例 2：
输入：s = “cbbd”
输出：“bb”
提示：
1 <= s.length <= 1000
s 仅由数字和英文字母组成
采用动态规划的思想
首先单个字母一定是回文串，其次判断长度为2的回文串，然后判断长度大于等于3的回文串
创建数组dp使得dp[i][j]=1表示i~j为一个回文串，易知当dp[i][j]=1时若存在s[i-1]=s[j+1]则dp[i-1][j+1]=1
所以存在状态转移方程 iff s[i]==s[j]&&dp[i+1][j-1]==1 then dp[i][j]=1
#include <string>
#include <iostream>
#include <vector>
using namespace std;
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
string longestPalindrome(string s) {
cout << s << endl;
int l = s.length();
if (l <= 1) {
return s;
} else if (l == 2) {
if (s[0] != s[1]) {
return s.substr(0, 1);
} else {
return s;
}
} else {
vector<vector<int> > dp(l, vector<int>(l));
string str = s.substr(0, 1);
for (int i = 0; i < l; ++i) {
dp[i][i] = 1;
if (i + 1 < l && s[i] == s[i + 1]) {
dp[i][i + 1] = 1;
str = s.substr(i, 2);
}
}
for (int len = 3; len <= l; len++)
{
for (int i = 0; i + len - 1 < l; i++) {
int j = len + i - 1;
if (s[i] == s[j] && dp[i + 1][j - 1] == 1)
{
dp[i][j] = 1;
str = s.substr(i, len);
}
}
}
cout << str << endl;
return str;
}
}
};
//leetcode submit region end(Prohibit modification and deletion)
int main() {
Solution s;
s.longestPalindrome("aacabdkacaa");
}