5. 最长回文子串
题目链接:5. 最长回文子串
题目内容:
题目就是要我们找s中的回文子串,还要是最长的。其实想想,暴力求解也行……就是遍历所有的子串,同时判断是不是回文串,是的话再和记录的最大长度maxlen比较,如果更长就更新。时间复杂度直接变成O(n^3)。
动态规划
优化的点在于,假设子串s[i~j]已经不是回文串了,s[i-1~j+1]也不是回文串,就不用再去判断是否是回文串了。用动态规划求解,dp[i][j]为true或者false,表示s[i~j]子串是or不是回文串,dp更新过程:
- dp[i][j] = true需要dp[i+1][j-1] = true同时s[i] = s[j];【注意i+1 >= j-1】
- 如果dp[i+1][j-1] = false,dp[i][j]直接为false;
- 如果s[i] != s[j],直接false;
- dp[i][i] = true;
代码实现(C++):
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
//如果s是空或者只有一个字符直接返回s,本身就是回文串
if(n < 2)
return s;
//dp记录s所有子串是否是回文串
vector<vector<bool>> dp(n,vector<bool>(n));
//单字符子串s[i]是回文串
for(int i = 0; i < n ; i++)
dp[i][i] = true;
//记录目前最长的子串长度和开始的下标
int maxLen = 1, idx = 0;
//L是子串的长度,按照长度来找子串
for(int L = 2; L <= n; L++){
//子串开始下标
for(int begin = 0; begin <= n-L; begin++){
//子串结束下标
int end = L - 1 + begin;
//判断当前子串是否是回文子串
if(s[begin] != s[end])
dp[begin][end] = false;
else{
if(L <= 3)
dp[begin][end] = true;
else
dp[begin][end] = dp[begin+1][end-1];
}
//如果当前子串是回文子串,其长度和maxlen对比
if(dp[begin][end] && L > maxLen){
maxLen = L;
idx = begin;
}
}
}
//返回最长回文子串
return s.substr(idx, maxLen);
}
};
动态规划也是判断所有子串是否是回文串,但是相较于暴力求解,用dp来存储每个子串是否是回文串,一个子串s[i~j]是否是回文串可以直接通过dp[i+1][j-1]得到,时间复杂度是O(1),因此整体时间复杂度是O(n^2)。同时dp需要额外的空间,空间复杂度是O(n^2)。
注意上述遍历子串,最外层是通过子串长度来控制的,如果外层是子串开始下标begin,内层是子串结束下标end,dp[begin][end]根据dp[begin+1][end-1]决定是true还是false,需要先有dp[begin+1][end-1],即dp[begin+1]这一行要先求得值,begin要从大到小:
//注意begin从大到小,从后往前
for(int begin = n - 2; begin >= 0; begin --){
for(int end = begin + 1; end < n; end ++){
if(s[begin] != s[end])
dp[begin][end] = false;
else{
if(end - begin < 3)
dp[begin][end] = true;
else
dp[begin][end] = dp[begin+1][end-1];
}
if(dp[begin][end] && end - begin + 1 > maxLen){
maxLen = end - begin + 1;
idx = begin;
}
}
}
中心扩展算法
动态规划需要dp来存储所有子串是否是回文串,其实是并不需要的。如果以一个字符串作为中心,然后朝两边扩展,s[i~j]变成s[i-1~j+1],s[i-1~j+1]是否是回文串直接依赖于s[i~j]的,如果s[i~j]不是回文串了,再朝两边扩展是没有意义的。这样减少了部分子串的判断,同时减少了dp这个二维数组。当s[i~j]不能朝两边扩展的时候,当前的s[i~j]就是以某个字符为中心的最长的回文子串,此时与maxlen比较,判断是否更新maxlen即可。
这样的中心就是s中的n个字符。但是需要注意的是,如果只是以这个字符作为中心,从s[i~i]开始,,遍历的永远都是长度为奇数的子串。还需要遍历长度为偶数的子串,即从s[i~i+1]这样的子串开始。代码如下(C++):
class Solution {
public:
//查找以一个字符或者两个字符为中心的最长回文子串
pair<int, int> expandAroundCenter(const string& s, int left, int right) {
while (left >= 0 && right < s.size() && s[left] == s[right]) {
--left;
++right;
}
//返回左右下标
return {left + 1, right - 1};
}
string longestPalindrome(string s) {
int start = 0, end = 0;
//所有字符都作为中心字符去查找最长的回文子串
for (int i = 0; i < s.size(); ++i) {
auto [left1, right1] = expandAroundCenter(s, i, i);
auto [left2, right2] = expandAroundCenter(s, i, i + 1);
//更新
if (right1 - left1 > end - start) {
start = left1;
end = right1;
}
//更新
if (right2 - left2 > end - start) {
start = left2;
end = right2;
}
}
return s.substr(start, end - start + 1);
}
};
这里时间复杂度也是O(n^2),但是提交的时候运行时间,比动态规划少了20倍……
214. 最短回文串
题目链接:214. 最短回文串
题目内容:
题目的意思是要在字符串s的前面添加字符(字符数量≥1,可以说是加一个字符串s’),添加字符的目的是为了让s变成一个回文串。 另外需要最终的s’+s是所有答案中的最短的,也就是要添加的s’最短。
要使得s’+s是回文串很简单,直接把s的逆序加在s的前面,肯定是个回文串;或者把s第一个字符后的子串逆序加在s前,也肯定是回文串,是以s首字符为回文中心的。
上面的方法是可以得到回文串的,但是要怎么样才能使得最终的回文串更短呢。
回文串有一个回文中心,回文中心两边是长度相等的、一段的逆序与另外一段完全相同的两段子串。现在在s的前面加一些字符能够使得s’+s是回文串,那么反过来想,删除s中末尾一段与s’的逆序相同的子串,剩下的子串也是回文串。 所以只要能够在s中找到一段以s首字符开始的最长的回文串,就能保证在此基础上,将s中除这个回文子串剩下的子串,逆序加在s前面得到的回文串是最短的。那么我们要怎么寻找s中是回文的前缀呢?假设这个回文子串是s1,s除s1外的子串s-s1用s2表示,s^是s的逆序(反转)后的字符串,s1在s^中其实就是后缀,由于s1是回文串,所以s1 = reverse(s1)。所以把s^看作是查找串,s看作是模式串,两者其做字符串匹配,用kmp算法,最终当s^遍历到最后一个字符的时候,s是第i个字符,那么0~i这段子串就是s1,即最长的前缀回文串:
整体解题步骤是:
- 找s1:s反转后的字符串s^作为查找串,s作为模式串,用kmp算法去做字符串匹配;算法结束的时,即遍历到s^最后一个字符时,对应s中第i个字符,0~i即为查找的最长前缀回文串;
- 将s-s1反转,并加在s前面,即得到了答案;
代码实现(C++):
class Solution {
public:
int strStr(string haystack, string needle) {
int n = needle.size();
vector<int> next(n, 0);
//next数组中存的是对应下标处子串【包括下标位置】的最长前后缀的长度
for(int i = 1; i < n; i++){
int j = next[i-1];
while(j>0 && needle[j] != needle[i])
j = next[j-1];
if(needle[i] == needle[j])
j++;
next[i] = j;
}
int pos = 0, j = 0;
while(pos < haystack.size()){
while(j>0 && haystack[pos] != needle[j])
j = next[j-1];
if(haystack[pos] == needle[j]){
pos++;
j++;
}
else
pos++;
}
//循环结束时,pos=haystack.size(), j对应子串长度,而不是结束下标,下标为j-1
return j;
}
string shortestPalindrome(string s) {
//s为空或者只有一个字符的时候,直接返回
if(s.empty() || s.size() == 1)
return s;
string re_s = s;
reverse(re_s.begin(),re_s.end()); //得到s的逆序re_s
//idx其实是前缀回文子串s1的长度
int idx = strStr(re_s,s);
//即s一整个是回文串
if(idx == s.size())
return s;
//反转s2,实际就是re_s前面一截,并加在s前面
return re_s.substr(0, s.size() - idx) + s;
}
};
这道题目在找s中最长前缀回文串的时候,没有使用上面题目的动态规划,是因为本题很明确,这个回文串是s的前缀,是从s第一个字符开始的子串。而要找s的最长回文子串,这个子串开始的位置是不知道的。
另外,如果题目换成在s的后面加上s’,使得s+s’是最短回文串,同样的方法,不过kmp的时候,s是查找串,s^是模式串。
336. 回文对
题目链接:336. 回文对
题目内容:
理解题意,是要在words中找到两个字符串words[i]、words[j],使得words[i] + words[j]是回文串。这题目不是和上面题目很像嘛!可以分情况讨论:文章来源:https://www.toymoban.com/news/detail-701092.html
- words[i]和words[j]互为对方的逆序,比如words[i] = “abcd”,words[j] =“dcba”,那么words[i] + words[j]和words[j] + words[i]都是回文的;
- words[i]前缀本身是回文,words[j]是words[i]以回文前缀下标结束点m为开始的后缀的逆序,那么words[j] + words[i]是回文的;比如words[i] = “abcbadef”,words[j] = “fed"或者"fed”;
- words[i]后缀本身是回文,words[j]是words[i]中回文后缀下标开始点m为结束的前缀的逆序,那么words[i] + words[j]是回文的;比如words[i] = “defabcba”,words[j] = “fed”;
还没做,代码待更……文章来源地址https://www.toymoban.com/news/detail-701092.html
到了这里,关于【leetcode 力扣刷题】回文串相关题目(KMP、动态规划)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!