【问题描述】
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example:
Input: "cbbd"
Output: "bb"
问题来源：longest-palindromic-substring
【解题分析】
要寻找一个最长的连续回文子串。 我们定义dp[i][j]为从i到j的字符串是不是回文串。 依据回文的规则： 1. 如果s[i] = s[j]，那么是否是回文串决定于dp[i+1][j-1] 2. 如果s[i]!=s[j]，那么dp[i][j] = 0 3. 动态规划是按照字符串的长度从1到n进行(不然dp初始化为0，就算整个字符串是一个回文串，它也只会截取到某一子回文串)。 代码时间复杂度为O(N^2)，空间复杂度为O(N^2)。
【源代码】
class Solution {
public:
string longestPalindrome(string s) {
vector<vector<bool> > dp(s.length(),vector<bool>(s.length(),0));
if (s.length() == 0 || s.length() == 1) {
return s;
}
for (int i = 0; i < s.length(); i++) {
for (int j = 0; j < s.length(); j++) {
if (i >= j) {
dp[i][j] = 1;
}
}
}
int maxLength = 1;
int left = 0;
int right = 0;
for (int k = 1; k < s.length(); k++) {
for (int i = 0; k + i < s.length(); i++) {
int j = k + i;
if (s[i] != s[j]) {
dp[i][j] = 0;
} else {
dp[i][j] = dp[i+1][j-1];
if (dp[i][j]) {
if (k + 1 > maxLength) {
maxLength = k + 1;
left = i;
right = j;
}
}
}
}
}
return s.substr(left,right-left+1);
}
};
