目录
1,题目描述
英文描述
中文描述
2,解题思路
方法一:中心扩展法
方法二:动态规划
3,AC代码(C++)
方法一:中心扩展法
方法二:动态规划
4,解题过程
第一博
第二搏
第三搏
1,题目描述
英文描述
Given a string s, find the longest palindromic(回文) substring(子串) in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"
中文描述
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1:
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2:
输入: "cbbd"
输出: "bb"
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2,解题思路
方法一:中心扩展法
- 遍历一遍字符串,都每一个字符分别进行奇数型(cabac)和偶数型(baab)扩展(也就是分别向左右两边遍历字符,看满足回文条件的最远距离在哪里);
- 记录扩展后获得的最大字符串长度,并更新结果;
方法二:动态规划
参考@力扣官方题解【最长回文子串】。有人把动态规划总结为填表,确实非常有道理。
本题关键有两点。状态转移方程如何编写(怎样填表),何种方式遍历(何种方式填表):
1,状态转移方程:
dp[i][j] = (dp[i-1][j-1] && s[i] == s[j])即字符子串s[i, j](包括s[i]和s[j])是回文子串的前提是,s[i+1][j-1]是回文子串 且 s[i]==s[j]。比如abcbadc中,i和j分别指向0和4,s[0, 4](abcba)是回文子串的前提是,s[1, 3](bcb)是回文子串 且 s[0]==s[4]
分析回文子串的特征
- 单个字符为回文子串;
- 两个字符若相等,则也为回文子串;
- 大于等于三个字符时,就需要dp[i][j] = (dp[i-1][j-1] && s[i] == s[j])进行填表了
2,何种方式遍历:
注意到状态转移方程中 dp[i][j] = (dp[i-1][j-1] && s[i] == s[j]),即要算出当前i,j所指状态dp[i][j],需要提前计算出其左下角的状态dp[i-1][j-1]
如图,数字表明遍历顺序,箭头所指表示先有2才能有6的结果:
3,AC代码(C++)
方法一:中心扩展法
class Solution {
public:
pair<int, int> extendPali(string& s, int left, int right){
while(left >= 0 && right < s.length() && s[left] == s[right]){
left--;right++;
}
return {left + 1, right - 1};
}
string longestPalindrome(string s) {
int start = 0, end = 0;
pair<int, int> tem;
int n = s.length();
for(int i = 0; i < n; i++){
tem = extendPali(s, i, i); //奇数型扩展
if(tem.second - tem.first > end - start){
start = tem.first;
end = tem.second;
}
tem = extendPali(s, i, i + 1); //偶数型扩展
if(tem.second - tem.first > end - start){
start = tem.first;
end = tem.second;
}
}
return s.substr(start, end - start + 1);
}
};
方法二:动态规划
class Solution {
public:
string longestPalindrome(string s) {
string ans;
int start = 0, end = 0;
int n = s.length();
vector<vector<bool>> dp(n, vector<bool>(n));
for(int i = n - 1; i >= 0; i--){
for(int j = i; j < n; j++){
if(j - i == 0){
dp[i][j] = true; //单个字符必定为回文子串
}
else if(j - i == 1){
dp[i][j] = (s[i] == s[j]); //仅有两个字符时 两字符相等即回文子串
}
else{
dp[i][j] = (dp[i+1][j-1] && s[i] == s[j]); //s[i,j]为回文子串的前提是:s[i+1,j-1]是回文子串 && s[i]==s[j]
}
//由于是从右下角开始的状态转移 且输出的是第一个最长回文子串 所以这里加上等号 输出编号靠前的最长回文子串
if(dp[i][j] && (j - i >= end - start)){
start = i;
end = j;
}
}
}
return s.substr(start, end - start + 1);
}
};
4,解题过程
第一博
暴力O(N^3),双重循环界定子串范围,判断子串是否为回文字符串;
class Solution {
public:
bool isPaliString(string s){
int i = 0, j = s.length() - 1;
while(i < j){
if(s[i] != s[j]){
return false;
}else{
i++;j--;
}
}
return true;
}
string longestPalindrome(string s) {
string ans, tem;
int n = s.length();
for(int i = 0; i < n; i++){
for(int j = i; j < n; j++){
tem = s.substr(i, j - i + 1);
if(isPaliString(tem) && ans.length() < tem.length()){
ans = tem;
}
}
}
return ans;
}
};
第二搏
参考@力扣官方题解【最长回文子串】中心扩展法,时间:O(N^2),空间:O(1)。需要区分奇/偶数扩展。
第三搏
参考@liweiwei1419【动态规划、中心扩散、Manacher 算法】,里面扩展了对于动态规划整体思路的讲解,堪称教科书式介绍!强烈推荐!(可是没有C++的代码)
关于C++的代码实现,可以参考@力扣官方题解【最长回文子串】