大家好,又见面了,我是你们的朋友全栈君。
1. 题目来源
链接:lc5. 最长回文子串
2. 题目解析
方法一:枚举
回文串一共有两种,即长度为奇数的回文串,长度为偶数的回文串。我们可以枚举回文串的中心(偶数长度回文串假想一个中心就行了),然后分别拿两个指针 l = i - 1
,r = i + 1
向左右两边同时拓展,若 s[l]=s[r]
则,l --, r ++
。一直进行该操作,直到不等或一方到达边界位置。
我们针对每一个枚举位置 i
,都考虑其两种情况,即偶数,奇数都考虑一遍,取个最大的就行了。
时间复杂度: O ( n 2 ) O(n^2) O(n2)
至于本问题,还有一些非常秀的方法。dp
在这也只能达到 O ( n 2 ) O(n^2) O(n2) 的时间复杂度,且还要开辟 dp
数组。
其中,字符串哈希+二分,貌似能够做到 O ( n l o g n ) O(nlogn) O(nlogn) 的时间复杂度。
至于那个,马拉车算法,之前简单看过,专门解决最长回文子串问题,时间复杂度能达到 O ( n ) O(n) O(n),不过可拓展性非常之低。
本题采用的中心拓展思想在别的问题中也能用到~
代码:
// 暴力直接算,即中心扩散,时间复杂度为O(n^2) 字符串最好能在1000以内的长度
// 动规可以算,时间复杂度为O(n^2)
// 马拉车算法,专门解决最长回文子串问题,时间复杂度能达到O(n)
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
string res;
for (int i = 0; i < n; i ++ ) {
// 处理回文串长度为奇数的情况
int l = i - 1, r = i + 1;
while (l >= 0 && r < n && s[l] == s[r]) l -- , r ++ ;
if (res.size() < r - l - 1) res = s.substr(l + 1, r - l - 1); // 左闭右开区间
// 处理回文串为偶数的情况
l = i, r = i + 1;
while (l >= 0 && r < n && s[l] == s[r]) l -- , r ++ ;
if (res.size() < r - l - 1) res = s.substr(l + 1, r - l - 1);
}
return res;
}
};
方法二:区间 dp
更新于 2021 年 4 月 16 日晚。字符串区间 dp 的题目比较少,经典有 lc 87 题,dfs 超时,区间 dp 可解,lc 87 是很难的一道题。
官方题解思路蛮不错的,三种方法都有涉及。
思路:
f[i][j]
表示s[i : j]
能否构成回文串。- 当区间长度为 1 时,必然构成一个回文串,即
f[i][i] = true;
。 - 字符串区间
dp
最重要的就是 枚举长度,要理解这个枚举顺序。 - 枚举长度,再枚举左边界,通过长度确定右边界坐标。
- 若右坐标合法,那么判断左右坐标对应字符是否相等,若不等则
f[i][j]
不构成回文串。否则,如果区间长度小于 3 的话,那么就直接是f[i][j]=true
,因为只有两个数字的话,f[i+1][j-1]
直接交换位置…造成状态的错误更新。否则区间长度大于等于三时,s[i : j]
首先两侧字符相等,那么f[i][j] = f[i+1][j-1]
。这两者是等价的。进行状态转移即可。
时间复杂度: O ( n 2 ) O(n^2) O(n2)
空间复杂度: O ( n 2 ) O(n^2) O(n2)
很经典的一道题目,三种解法中的任一种都是非常经典且值得学习的。中心拓展、区间 dp
都是非常常用的思想,而马拉车不常用,但它却是能 O ( n ) O(n) O(n) 的解决该问题!日后再补吧,以前总结了,又忘了…
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
if (n < 2) return s;
// f[i][j] 表示 s[i:j] 这一段是回文串,区间 dp
vector<vector<bool>> f(n, vector<bool>(n));
// 长度为 1 的串必然是回文的
for (int i = 0; i < n; i ++ ) f[i][i] = true;
// 最短的回文串长度就是 1,在这初始化 mx=0 的话会出错
// 可能整个串中都没有长度大于 2 的回文串,那么最后 substr() 的时候就会出错了,如 "ac"
int mx = 1, l = 0;
for (int len = 2; len <= n; len ++ ) {
// 枚举子串长度
for (int i = 0; i < n; i ++ ) {
// 枚举左边界。根据长度得到右边界下标
int j = len + i - 1; // [i, j] 有 j-i+1 个数
if (j >= n) break; // 右边界越界,左区间不需要再向右了,退出当前循环
if (s[i] != s[j]) f[i][j] = false; // [i,j] 不构成回文串
else {
// 等价 if (len < 3) 因为只有两个数字的话,f[i+1][j-1] 直接交换位置...
if (j - i < 3) f[i][j] = true; // [i,j] 长度小于等于 2 只要s[i]==s[j]就构成回文串
else f[i][j] = f[i + 1][j - 1]; // 可能构成回文串,取决于 s[i+1:j-1] 是否能构成回文串
}
if (f[i][j] && j - i + 1 > mx) {
mx = j - i + 1;
l = i;
}
}
}
return s.substr(l, mx);
}
};
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/164020.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...