广西网站建设电话,1688成品网站源码,国内十大搜索引擎网站,做饰品一般用什么网站做首饰LeetCode 647- 回文子串
题目链接#xff1a;力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台
题目描述#xff1a;给你一个字符串 s #xff0c;请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子…LeetCode 647- 回文子串
题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
题目描述给你一个字符串 s 请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串即使是由相同的字符组成也会被视作不同的子串。
解题思路
确定dp数组dp table以及下标的含义
可能上来就会想dp[i][j]定义成在这个范围内回文子串的个数这样定义不好找递推关系定义成dp[i][j] 表示s在下标[i,j]区间内是否为回文串。可以很容易找到递推关系也就是dp[i][j]是否是回文子串我们只需要先判断s[i] 是否等于s[j]然后在看dp[i1][j-1]也就是缩小范围后是否是回文子串就能推出dp[i][j]
确定递推公式
首先分两种情况当前字符相等和不相等
不相等时我们不做处理在初始化的时候将所有值都设置为false。
若相等则需要分三种情况 情况一i和j的差值为0也就是指向同一个字符a一定是回文子串也就是dp[i][j] true情况二i和j的差值为1,也就是这俩字符相等且其中没有别的字符如aa,也就是dp[i][j] true情况三i和j的差值大于1也就是中间有很多字符这时我们就需要判断其子串是否为回文串了也就是看dp[i1][j-1]是否为真为真则dp[i][j] true否则不处理。 故递推公式就是
if (s[i] s[j]) {if (j - i 1) { // 情况一 和 情况二result;dp[i][j] true;} else if (dp[i 1][j - 1]) { // 情况三result;dp[i][j] true;}
}
dp数组如何初始化
由于我们开始不知道哪些是回文串所以dp数组在最开始我们全部都初始化为false。
确定遍历顺序
依据递推公式我们可以看出每次更新我们都是从左下角往右更新所以我们从下往上从左往右遍历dp数组来更新。
举例推导dp数组
class Solution {
public:int countSubstrings(string s) {vectorvectorbool dp(s.size(), vectorbool(s.size(), false));int result 0;for (int i s.size() - 1; i 0; i--) { // 注意遍历顺序for (int j i; j s.size(); j) {if (s[i] s[j]) {// 当前字符相等后才来判断i j 差值也就是判断中间是否有别的字符if (j - i 1) { result;dp[i][j] true;} else if (dp[i 1][j - 1]) { // 情况三result;dp[i][j] true;}}}}return result;}
};
总结
这题的dp数组定义需要思考一下我们一般都直观的定义为题目需要求解的答案。而这题是定义成了是否为回文串因为这样才能找到递推的规律。以后做题要注意动态规划需要找递推公式这样想着来定义dp数组。
LeetCode 516.最长回文子序列
题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
题目描述给你一个字符串 s 找出其中最长的回文子序列并返回该序列的长度。
子序列定义为不改变剩余字符顺序的情况下删除某些字符或者不删除任何字符形成的一个序列。
解题思路
1.确定dp数组dp table以及下标的含义
dp[i][j]s字符串在[i,j]区间内最长回文子串的长度。
2.确定递推公式
我们需要分情况讨论首先字符串1与字符串2当前字符相等或不等的情况
相等则不进行操作。也就是dp[i][j] dp[i-1][j-1] 2图示 不相等时有两种情况我们取其中的最大值故 dp[i][j] min(dp[i-1][j],dp[i][j-1])
3.dp数组如何初始化
当 i j的时候值为1其余全部都为0也就是每个字符串本身是回文子串其余的全部默认为0。
4.确定遍历顺序
依据递推公式我们可以看出dp[i][j]是由左下角的状态推导而来故我们应该从下往上从左往右遍历
5.举例推导dp数组
class Solution {
public:int longestPalindromeSubseq(string s) {vectorvectorint dp(s.size(), vectorint(s.size(), 0));for (int i 0; i s.size(); i) dp[i][i] 1;for (int i s.size() - 1; i 0; i--) {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数组的含义要将其牢记在心这样才能真正弄懂一道题。
