5. Longest Palindromic Substring
Description
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"
Analysis
非常经典的一个问题，求最长回文字串。
这道题看似容易解决，似乎将字符串逆置后，和原字符串作比较，找出两者的最长公共字串即可。
但实际上此种解法只是看似可行,比如对于babad，可以用这种方法找到其最长回文字串。但如果一个较长的非回文字串出现在原字符串中，比如abcdefghg`,那么很容易就能证明，上述算法会得出一个错误的答案，所以需要换一个角度进行考虑。
那么下一个比较容易想到的方法就是暴力破解了，穷举所有字串，判断其是否是回文字符串。但这样的时间空间复杂度都相当高(O（N^3）)，所以只能放弃这个方法。
考虑构成回文串的条件，如果区间(i,j)能构成回文串，那么(i+1,j-1)一定也能构成回文串。所以我们可以以一个字母为”mid”,不断向两边扩张，直到不构成回文串为止。计算回文串长度和起始位置。
待mid指针遍历过所有字母之后，通过之前维护的max_left,max_len两个变量，计算出最长回文字符串。
时间复杂度为O（N^2),空间复杂度O（1），代码耗时6ms
code
class Solution {
public:
string longestPalindrome(string s) {
if(s.size()<2)
return s;
int max_len=1,max_left=0;
for(int mid=0;mid<s.size();){
int left=mid;
int right=mid;
while(right<s.size()-1&&s[left]==s[left+1]) ++left;
mid=left+1;
while(right<s.size()-1&&left>0&&s[left-1]==s[right+1]){--left; ++right;}
int new_len=right-left+1;
if(new_len>max_len){max_left=left; max_len=new_len;}
}
return s.substr(max_left,max_len);
}
};
动态规划解法
刚才在上一种解法中，已经找到了一个串为回文串的条件。
- dp[i][j]==true为串s[i][j]为回文
- 将dp[i][i]，dp[i][i-1]初始化为true，其余全为false(即一个或两个字母组成的字符串均认为是回文)
- 之后穷举字串长度的值，对于其是否为回文，取决于
(s[i] == s[j] && dp[i+1][j-1] == true)
时间复杂度O（N^2),空间复杂度O(N^2)
code
/*Dynamic programming*/
class Solution {
public:
string longestPalindrome(string s) {
if(s.size()<2)
return s;
int max_len=1,max_left=0,s_len=s.size();
bool dp[s_len][s_len]={false};
dp[0][0]=true;
for(int i=1;i<s_len;++i){
dp[i][i]=true;
dp[i][i-1]=true;
}
for(int len=2;len<s_len;++len){
for(int i=0;i<=s_len-len;++i){
if(s[i]==s[i+len-1]&&dp[i+1][i+len-2]){
dp[i][i+len-1]=true;
if(len>max_len){
max_left=i;
max_len=len;
}
}
}
}
return s.substr(max_left,max_len);
}
};