微 网站,怎么去管理好一个团队,中国商标查询网官网,做网站 用哪种647. 回文子串
题目#xff1a;
给你一个字符串 s #xff0c;请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串#xff0c;即使是由相…647. 回文子串
题目
给你一个字符串 s 请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串即使是由相同的字符组成也会被视作不同的子串。
示例 2
输入aaa输出6解释6个回文子串: a, a, a, aa, aa, aaa
dp数组的含义
观察到不能之间用题目所求套上dp数组看不出意义那就看题目里有没有性质可以利用。这里用的是回文串的性质。
如果i1到j-1是回文串那么如果i和j的值相等i到j也是回文串。
布尔类型的dp[i][j]表示区间范围[i,j] 注意是左闭右闭的子串是否是回文子串如果是dp[i][j]为true否则为false。
输入aaadp图如下
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]) {if (j - i 1) { // 情况一 和 情况二result;dp[i][j] true;} else if (dp[i 1][j - 1]) { // 情况三result;dp[i][j] true;}}}}return result;}
};
可以观察到如果字符串匹配有两个判断链条链条有result记录结果以及修改当前dp值为1第一个遍历i的循环是从大到小遍历。
递推公式
当s[i]与s[j]不相等等于 不是回文串默认false不用操作
当s[i]与s[j]相等时有如下三种情况
情况一下标i 与 j相同同一个字符例如a当然是回文子串单个回文子串情况二下标i 与 j相差为1例如aa也是回文子串两个回文子串情况三下标i 与 j相差大于1的时候例如cabac此时s[i]与s[j]已经相同了我们看i到j区间是不是回文子串就看aba是不是回文就可以了那么aba的区间就是 i1 与 j-1区间这个区间是不是回文就看dp[i 1][j - 1]是否为truedp[i 1][j - 1]的定义是表示区间范围[i,j]的子串是否是回文子串。超过两个的回文子串
if (s[i] s[j]) {if (j - i 1) { // 情况一和情况二i和j相等的时候01 相差111所以两种情况包含在内result;dp[i][j] true;} else if (dp[i 1][j - 1]) { // 情况三result;dp[i][j] true;}
}
初始化都为false 默认为ture就全是回文子串了
遍历顺序由于递推公式中情况三是根据dp[i 1][j - 1]是否为true来对dp[i][j]进行赋值true
这图可以看出dp[i][j]是由左下的dp[i 1][j - 1]判断的所以顺序需要
从下到上从左到右来保证递推公式可以推导。
总代码
在途中用result收集为子串的情况末尾返回完成题目。
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]) {if (j - i 1) { // 情况一 和 情况二result;dp[i][j] true;} else if (dp[i 1][j - 1]) { // 情况三result;dp[i][j] true;}}}}return result;}
}; 516.最长回文子序列
题目
给定一个字符串 s 找到其中最长的回文子序列并返回该序列的长度。
示例 1: 输入: bbbab 输出: 4 一个可能的最长回文子序列为 bbbb。
安装原始排序不变不需要连续凑成回文子序列。
dp数组含义
dp[i][j]字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。
递推公式
s[i]与s[j]相同
dp[i][j] dp[i 1][j - 1] 2;意为在原来是回文子序列的基础加上这两个相等的长度
s[i]与s[j]不相同
说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子序列的长度那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。
加入s[j]dp[i 1][j]。这个dp[i 1][j]表示加了s[j]的最大回文子序长度可以说加了s[j]的最大长度
加入s[i]dp[i][j - 1]。这个dp[i][j - 1]表示加了s[i]的最大回文子序长度可以说加了s[i]的最大长度
dp[i][j]取两者可能的最大长度即dp[i][j]可以从加了那个字符推出最大长度即dp[i][j] max(dp[i 1][j], dp[i][j - 1]);
初始化 首先要考虑当i 和j 相同的情况从递推公式dp[i][j] dp[i 1][j - 1] 2; 可以看出i 1 和 j - 1 一直往中间缩给的字符集是奇数的话会缩到一个字符上这个时候dp[i][j]等于1即一个字符的回文子序列长度就是1。偶数个的话会彼此交过就是0
vectorvectorint dp(s.size(), vectorint(s.size(), 0));
for (int i 0; i s.size(); i) dp[i][i] 1;
遍历顺序 遍历i的时候一定要从下到上遍历保证下一行的数据是经过计算的。
j的话正常从左向右
总代码
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];}
};
