大型视频网站开发,平面设计和电子商务哪个好,淘宝电商怎么做,杭州网站建站平台目录 回文子串
最长回文子串 分割回文串 IV 分割回文串 II 最长回文子序列 让字符串成为回文串的最少插入次数 回文子串
647. 回文子串 思路#xff0c;i j表示改范围内是否为回文串#xff0c;
②倒着遍历是为了取出dp[i 1][j - 1]
③i j 只有一对#xff0c;不会重复…目录 回文子串
最长回文子串 分割回文串 IV 分割回文串 II 最长回文子序列 让字符串成为回文串的最少插入次数 回文子串
647. 回文子串 思路i j表示改范围内是否为回文串
②倒着遍历是为了取出dp[i 1][j - 1]
③i j 只有一对不会重复其实就是遍历
参考代码
class Solution {
public:int countSubstrings(string s) {int n s.size();vectorvectorbool dp(n, vectorbool(n));int ret 0;for(int i n - 1; i 0; i--){// dp[i][i] true;// for(int j i 1; j n; j)// {// if(s[i] s[j])// dp[i][j] j - i 1 ? dp[i 1][j - 1] : true;// if(dp[i][j]) ret;//判断每一次// }for(int j i; j n; j){if(s[i] s[j])dp[i][j] j - i 1 ? dp[i 1][j - 1] : true;//只有最后一层会越界但是if(dp[i][j])ret;}}// return ret n;return ret;}
};
最长回文子串
5. 最长回文子串 思路区间[i, j] 是true时候再判断
参考代码
class Solution {
public:string longestPalindrome(string s) {int n s.size();vectorvectorint dp(n, vectorint(n));int maxlen 1, begin 0;for(int i n - 1; i 0; i--){dp[i][i] true;for(int j i 1; j n; j){if(s[i] s[j])dp[i][j] j - i 1 ? dp[i 1][j - 1] : true;if(dp[i][j] j - i 1 maxlen)maxlen j - i 1, begin i;}}return s.substr(begin, maxlen);}
}; 分割回文串 IV
1745. 分割回文串 IV 用区间[i, j]即可分成三段 只要i j 不同三段必不相同
参考代码
class Solution {
public:bool checkPartitioning(string s) {int n s.size();vectorvectorbool dp(n, vectorbool(n));for(int i n - 1; i 0; i--)for(int j i; j n; j)if(s[i] s[j])dp[i][j] j - i 1 ? dp[i 1][j - 1] : true;for(int i 1; i n - 2; i)for(int j i; j n - 2; j)if(dp[0][i - 1] dp[i][j] dp[j 1][n - 1])return true;return false;}
}; 分割回文串 II
132. 分割回文串 II 刚开始打算用dp[i, j]区间内需要的次数 发现逻辑就不对以左右单个字符拎出来在min剩下的最小分割的位置很可能在中间某个位置所以打算重新遍历数组和139. 单词拆分的思路很像[0, i] 区间存放的就是最小分割次数 参考代码
class Solution {
public:int minCut(string s) {// int n s.size();// vectorvectorint dp(n, vectorint(n));// for(int i n - 1; i 0; i--)// {// for(int j i 1; j n; j)// {// if(s[i] s[j])// dp[i][j] dp[i 1][j - 1];// else// dp[i][j] min(dp[i 1][j], dp[i][j - 1]) 1;// }// }// return dp[0][n - 1];int n s.size();vectorvectorbool dp(n, vectorbool(n));for(int i n - 1; i 0; i--)for(int j i; j n; j)if(s[i] s[j]) dp[i][j] j - i 1 ? dp[i 1][j - 1] : true;vectorint times(n, INT_MAX);times[0] 0;for(int i 1; i n; i){if(dp[0][i]) times[i] 0;elsefor(int j 1; j i; j)if(dp[j][i])times[i] min(times[i], times[j - 1] 1);}return times[n - 1];}
}; 最长回文子序列
516. 最长回文子序列 因为[i ,j] 表示的是区间内的最长回文子序列这里我不怎么能直接理解这里的j每次往后走应该是去尝试匹配s[i]那么有人会说s[i] 可能和[i 1, j - 1] 区间内有匹配了那么用s[j]去匹配不就少了一个吗其实不然这时候中间不管是否和s[i]相同,【 s[i] ,中间字符s[j] 】就是一个回文子序列这样是最大的如果不相等因为说了状态表示的是区间内的最长回文子序列这时候去已经有的区间里面找最长的已知区间就是[i 1, j] 和 [i , j 1]那为什么不去[i, j] 里找因为没有啊这时候dp[i][j]是左值呀
参考代码
class Solution {
public:int longestPalindromeSubseq(string s) {int n s.size();vectorvectorint dp(n, vectorint(n, 1));for(int i n - 1; i 0; i--){for(int j i 1; j n; j){if(s[i] s[j])dp[i][j] j - i 1 ? dp[i 1][j - 1] 2 : j - i 1;elsedp[i][j] max(dp[i 1][j], dp[i][j - 1]);}}return dp[0][n - 1];}
}; 让字符串成为回文串的最少插入次数 1312. 让字符串成为回文串的最少插入次数 dp表示的是区间[i, j] 内需要添加的最小次数同样的道理如果不相等就是去消除s[i] 或者s[j]消除伴随着 1也就是dp[i][j] min(dp[i][j - 1], dp[i 1][j]) 1,你可能会感觉不对 有可能是min(dp[i][j - 2], dp[i 2][j])那么随之后面就要2但是这个时候可能s[i] 和s[j - 1]是相等的啊那么就多添加了一个字符
参考代码
class Solution {
public:int minInsertions(string s) {int n s.size();vectorvectorint dp(n, vectorint(n));for(int i n - 1; i 0; i--){for(int j i 1; j n; j){if(s[i] s[j])dp[i][j] dp[i 1][j - 1];elsedp[i][j] min(dp[i 1][j], dp[i][j - 1]) 1;}}return dp[0][n - 1];}
};
总结:通过区间[i, j]来表示每个区间是否为回文串 是的话在进行怎样怎样的操作
我的错误发生 i总是写错i, 注意力不集中
