长沙做网站建设公司哪家好,开网店卖什么适合新手,慈溪专业做网站公司,学院做网站的意义647. 回文子串 647. 回文子串
题目描述#xff1a;
给你一个字符串 s #xff0c;请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串
给你一个字符串 s 请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串即使是由相同的字符组成也会被视作不同的子串。
解题思路 算法思路 我们可以先「预处理」⼀下将所有⼦串「是否回⽂」的信息统计在 dp 表⾥⾯然后直接在表 ⾥⾯统计 true 的个数即可。 1. 状态表⽰ 为了能表⽰出来所有的⼦串我们可以创建⼀个 n * n 的⼆维 dp 表只⽤到「上三⻆部分」 即可。 其中 dp[i][j] 表⽰ s 字符串 [i, j] 的⼦串是否是回⽂串。 2. 状态转移⽅程 对于回⽂串我们⼀般分析⼀个「区间两头」的元素 i. 当 s[i] ! s[j] 的时候不可能是回⽂串 dp[i][j] 0 ii. 当 s[i] s[j] 的时候根据⻓度分三种情况讨论 • ⻓度为 1 也就是 i j 此时⼀定是回⽂串 dp[i][j] true • ⻓度为 2 也就是 i 1 j 此时也⼀定是回⽂串 dp[i][j] true • ⻓度⼤于 2 此时要去看看 [i 1, j - 1] 区间的⼦串是否回⽂ dp[i][j] dp[i 1][j - 1] 。 综上状态转移⽅程分情况谈论即可。 3. 初始化 因为我们的状态转移⽅程分析的很细致因此⽆需初始化。 4. 填表顺序 根据「状态转移⽅程」我们需要「从下往上」填写每⼀⾏每⼀⾏的顺序⽆所谓。 5. 返回值 根据「状态表⽰和题⽬要求」我们需要返回 dp 表中 true 的个数。 解题代码
class Solution {
public:int countSubstrings(string s) {int ns.size();vectorvectorbooldp(n,vector(n,false));for(int in-1;i0;i--){for(int ji;jn;j){if(s[i]s[j]){if(ij)dp[i][j]true;else if(i1j)dp[i][j]true;else dp[i][j]dp[i1][j-1];}}}int ret0;for(int i0;in;i){for(int ji;jn;j){if(dp[i][j]true)ret;}}return ret;}
};
5. 最长回文子串 5. 最长回文子串
题目描述
给你一个字符串 s找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同则该字符串称为回文字符串。 解题思路
647. 回文子串https://leetcode.cn/problems/palindromic-substrings/
在647题的基础上遍历所有dp表中为true的初始位置和长度
解题代码
class Solution {
public:string longestPalindrome(string s) {int ns.size();vectorvectorbooldp(n,vector(n,false));for(int in-1;i0;i--){for(int ji;jn;j){if(s[i]s[j]){if(ij)dp[i][j]true;else if(i1j)dp[i][j]true;else dp[i][j]dp[i1][j-1];}}}int length1;int begin0;for(int i0;in;i){for(int j0;jn;j)if(dp[i][j]truelengthj-i1){lengthmax(j-i1,length);begini;}}return s.substr(begin,length);}
};
