北京66中网站做的不怎么样呀,网站流量提供商,全球速卖通是什么平台,wordpress上一篇文章647. 回文子串
1、题目 给你一个字符串 s #xff0c;请你统计并返回这个字符串中 回文子串 的数目。
题目链接#xff1a;https://leetcode.cn/problems/palindromic-substrings/
2、代码
class Solution {
public:
//判断字符串是否为回文bool IsPalindrome(string s, …647. 回文子串
1、题目 给你一个字符串 s 请你统计并返回这个字符串中 回文子串 的数目。
题目链接https://leetcode.cn/problems/palindromic-substrings/
2、代码
class Solution {
public:
//判断字符串是否为回文bool IsPalindrome(string s, int start, int end){//特殊情况if(end start) return false;if(end start) return true;//一般情况for(int i start, j end; i j; i, j--){if(s[i] ! s[j]) return false;}return true;}int countSubstrings(string s) {//特殊情况if(s.size() 1) return s.size();//dp数组和初始化vectorint dp(s.size(), 0);dp[0] 1;//遍历for(int i 1; i s.size(); i){for(int j 0; j i; j){if(IsPalindrome(s, j, i)) dp[i];}dp[i] dp[i - 1];}return dp[s.size() - 1];}
};3、小结 使用dp[i]表示字符串中0-i的字符串中回文的个数通过内层循环判断添加第i个字符后增加的回文串个数再加上dp[i-1]即可得到答案。
516.最长回文子序列
1、题目 给你一个字符串 s 找出其中最长的回文子序列并返回该序列的长度。
题目链接https://leetcode.cn/problems/longest-palindromic-subsequence/
2、代码
class Solution {
public:int longestPalindromeSubseq(string s) {//dp数组和初始化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() - 2; 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];}
};3、小结 使用dp[i][j]表示字符串中i-j的最长回文串序列将dp[i][i]均初始化为1再根据s[i],s[j]的情况进行遍历递推。需要注意遍历是从上到下从左到右。
