网站运营繁忙,鞍山网站建设,wordpress主题 响应式,深圳室内设计公司50强647. 回文子串
给你一个字符串 s #xff0c;请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串#xff0c;即使是由相同的字符组成#…647. 回文子串
给你一个字符串 s 请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串即使是由相同的字符组成也会被视作不同的子串。 示例 1
输入s abc
输出3
解释三个回文子串: a, b, c示例 2
输入s aaa
输出6
解释6个回文子串: a, a, a, aa, aa, aaa
思路 /* dp[i][j]表示i到j的字符串是否是回文串 ij dp[i][j] true; j-i1 dp[i][j] true; j-i1 if(dp[i1][j-1] true) dp[i][j] true; 初始化为false 遍历顺序 从底往上从左到右 打印dp数组 */
代码
class Solution {
public:int countSubstrings(string s) {/*dp[i][j]表示i到j的字符串是否是回文串ij dp[i][j] true;j-i1 dp[i][j] true;j-i1 if(dp[i1][j-1] true) dp[i][j] true;初始化为false遍历顺序 从底往上从左到右打印dp数组*/vectorvectorintdp(s.size(),vectorint(s.size(),0));int result 0;for(int i s.size()-1;i0;i--){for(int j i;js.size();j){if(s[i]s[j]){if(j-i1){ dp[i][j] true;result;}else{if(dp[i1][j-1]){dp[i][j] true;result;}}}}}return result;}
};
516. 最长回文子序列
给你一个字符串 s 找出其中最长的回文子序列并返回该序列的长度。
子序列定义为不改变剩余字符顺序的情况下删除某些字符或者不删除任何字符形成的一个序列。 示例 1
输入s bbbab
输出4
解释一个可能的最长回文子序列为 bbbb 。示例 2
输入s cbbd
输出2
解释一个可能的最长回文子序列为 bb 。思路 /* dp[i][j]表示从i到j的最长回文子序列长度 s[i]s[j] dp[i][j] dp[i1][j-1]2; s[i]! s[j] dp[i][j] max(dp[i][j-1],dp[i1][j]); 初始化为1 遍历顺序 从左到右从下到上 打印dp数组 */ 代码
class Solution {
public:int longestPalindromeSubseq(string s) {/*dp[i][j]表示从i到j的最长回文子序列长度s[i]s[j]dp[i][j] dp[i1][j-1]2;s[i]! s[j]dp[i][j] max(dp[i][j-1],dp[i1][j]);初始化为1遍历顺序 从左到右从下到上打印dp数组*/vectorvectorintdp(s.size(),vectorint(s.size(),0));for(int i 0;is.size();i) dp[i][i] 1;for(int i s.size()-1;i0;i--){for(int j i1;js.size();j){if(s[i]s[j]) dp[i][j] dp[i1][j-1]2;elsedp[i][j] max(dp[i][j-1],dp[i1][j]);}}return dp[0][s.size()-1];}
};
还有很多瑕疵还需继续坚持
