中国建设银行网站-个人客户,wordpress调用评论数据,做网站 内容越多越好,wordpress后台打开很慢文章目录 示例1#xff1a;回文子串思路DP数组含义#xff08;注意#xff09;递推公式初始化遍历顺序#xff08;注意#xff09; 完整版注意点 示例2#xff1a;最长回文子序列思路DP数组含义递推公式初始化遍历顺序 完整版注意点另一种写法不能把DP数组全部初始化为1的… 文章目录 示例1回文子串思路DP数组含义注意递推公式初始化遍历顺序注意 完整版注意点 示例2最长回文子序列思路DP数组含义递推公式初始化遍历顺序 完整版注意点另一种写法不能把DP数组全部初始化为1的原因 回文串系列主要在于DP数组定义与递推过程中的遍历顺序与之前的子序列差别比较大。
示例1回文子串
647. 回文子串 - 力扣LeetCode
给你一个字符串 s 请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串即使是由相同的字符组成也会被视作不同的子串。
示例 1
输入s abc
输出3
解释三个回文子串: a, b, c示例 2
输入s aaa
输出6
解释6个回文子串: a, a, a, aa, aa, aaa提示
1 s.length 1000s 由小写英文字母组成
思路
如果做了很多这种子序列相关的DP题目在定义dp数组的时候 很自然就会想题目求什么我们就如何定义dp数组。绝大多数题目确实是这样不过本题如果我们定义dp[i] 为 下标i结尾的字符串有 dp[i]个回文串的话我们会发现很难找到递归关系。
因为dp[i] 和 dp[i-1] dp[i 1] 看上去都没啥关系。所以我们要看回文串的性质。
判断字符串S是否是回文如果我们知道 s[1]s[2]s[3] 这个子串是回文的那么只需要比较 s[0]和s[4]这两个元素是否相同如果相同的话这个字符串s 就是回文串。
因此递归关系是判断一个子字符串字符串的下表范围[i,j]是否回文依赖于子字符串下表范围[i 1, j - 1] 是否是回文。
DP数组含义注意
bool型dp[i][j]表示如果起点为i终点为j的区间该区间的子串是回文串 注意是左闭右闭那么dp[i][j]为true否则为false。
递推公式
判断区间[i,j]构成的子串是不是回文串只有三种情况
ij也就是本身的情况一个字符本身是一个回文串对应a的情况j-i1也就是i和j相邻的情况那么相邻的两个字符构成一个回文串也就是aa的情况dp[i1][j-1]是一个回文串也就是”aba“的情况
if(s[j]s[i]){if((j-i)1){//包括了ji和j-i1的情况也就是相邻的情况和重合(只有一个)的情况result;dp[i][j]true;}else if(dp[i1][j-1]){result;//外层多了一个也是回文串结果1dp[i][j]true;}
}初始化
vectorvectorbooldp(s.size(),vectorbool(s.size(),false));遍历顺序注意
注意在本题中是通过dp[i1][j-1]来推出dp[i][j]的状态因此i的状态要通过i1来推出。因此i的遍历必须是倒序遍历。
同时j是从j-1状态推出来因此j的遍历是正序遍历。
for(int is.size();i0;i--){for(int ji;js.size();j){if(s[j]s[i]){if((j-i)1){//字符本身或者是相邻字符result;dp[i][j]true;}else if(dp[i1][j-1]){//内部相等result;dp[i][j]true;}}}
}完整版
class Solution {
public:int countSubstrings(string s) {vectorvectorbooldp(s.size(),vectorbool(s.size(),false));int result0;for(int is.size()-1;i0;i--){//倒序的时候i的范围是[0,s.size()-1]for(int ji;js.size();j){if(s[j]s[i]){if((j-i)1){//这里包含了两种情况(j-i)1的情况和ji的情况result;dp[i][j]true;}else if(dp[i1][j-1]){result;//外层相等也是多了一个回文串dp[i][j]true;}}}}return result;}
};注意点
倒序遍历的时候i的范围是[0,s.size()-1]也就是说倒序结束条件应该是i0回文串主要是情况分析。是回文的情况只有三种 ij也就是本身的情况一个字符本身是一个回文串对应a的情况j-i1也就是i和j相邻的情况那么相邻的两个字符构成一个回文串也就是aa的情况dp[i1][j-1]是一个回文串也就是”aba“的情况
分析完这三种之后再写递推递推就比较好写了。
示例2最长回文子序列
516. 最长回文子序列 - 力扣LeetCode
给你一个字符串 s 找出其中最长的回文子序列并返回该序列的长度。
子序列定义为不改变剩余字符顺序的情况下删除某些字符或者不删除任何字符形成的一个序列。
示例 1
输入s bbbab
输出4
解释一个可能的最长回文子序列为 bbbb 。示例 2
输入s cbbd
输出2
解释一个可能的最长回文子序列为 bb 。提示
1 s.length 1000s 仅由小写英文字母组成
思路
本题是不连续的但是DP数组依然是按照回文系列定义[i,j]区间的方式来定义。
DP数组含义
字符串s在[i,j]范围内最长回文子序列的长度为dp[i][j]
递推公式
在判断回文子串的题目中关键逻辑就是看s[i]与s[j]是否相同。
如果相同那么在dp[i1][j-1]的基础上**2**。(此时还有ji的情况ji应该1)
如果不相同那么就在不包含的两种情况不包含s[i]或者不包含s[j]中选择最大值。
for(int is.size()-1;i0;i--){for(int ji;js.size();j){if(s[i]s[j]){if(ij) dp[i][j]1;//注意DP数组的定义是区间[i,j]内回文子序列最大长度else if(j0)dp[i][j]dp[i1][j-1]2;}else{dp[i][j]max(dp[i-1][j],dp[i][j-1]);}}
}初始化
vectorvectorintdp(s.size(),vectorint(s.size(),0));遍历顺序
遍历顺序同上一题i是倒序遍历j是正序遍历且ji本题不是ji了因为长度累加2
完整版
class Solution {
public:int longestPalindromeSubseq(string s) {vectorvectorintdp(s.size(),vectorint(s.size(),0));int result0;for(int is.size()-1;i0;i--){for(int ji;js.size();j){if(s[i]s[j]){if(ij) dp[i][j]1;//注意DP数组的定义是区间[i,j]内回文子序列最大长度else if(j0)dp[i][j]dp[i1][j-1]2;}else{dp[i][j]max(dp[i1][j],dp[i][j-1]);//一定要注意这里是从[i1,j]和[i,j-1]里面取值因为i是倒序遍历j是正序遍历}resultmax(result,dp[i][j]);}}return result;}
};注意点
注意本题是求回文子串内部最大长度而且不连续因此本题ji和j!i的情况就需要分开。ji的情况是长度1j!i且s[j]s[i]的情况是长度2。遍历顺序和不等情况下的取值也有关系如果是不等的情况那么去除当前取值应该在[i1,j-1]的范围里面取
另一种写法
也可以在初始化的时候单独处理ij的情况令dp[i][i]1
class Solution {
public:int longestPalindromeSubseq(string s) {//vectorvectorint dp(s.size(), vectorint(s.size(), 1));vectorvectorint dp(s.size(), vectorint(s.size(), 0));//不能用1来初始化二维数组需要用0为了避免s[i]!s[j]但是dp[i][j]1的情况for(int i0;is.size();i){dp[i][i]1;}for (int i s.size() - 1; i 0; i--) {//j直接从i1开始只处理2的情况for (int j i 1; j s.size(); j) {if (s[i] s[j]) {dp[i][j] dp[i 1][j - 1] 2;} else {dp[i][j] max(dp[i 1][j], dp[i][j - 1]);}}}return dp[0][s.size() - 1];}
};不能把DP数组全部初始化为1的原因
dp[i][j]表示从索引i到索引j的字符串的最长回文子序列的长度。
如果字符串s[i]和s[j]不相等且ji1如果直接让dp[i][j]的值为1但实际上因为s[i]和s[j]不相等所以它们不可能构成一个回文子序列dp[i][j]应当为0。
dp[i][j]应该被初始化为0因为在默认情况下如果没有找到任何回文子序列那么回文子序列的长度应该为0。只有当i等于j时也就是只有一个字符的时候我们才把dp[i][j]设置为1因为单个字符自身就是一个长度为1的回文子序列。
