上海网站建设公司哪个好,网站建设是啥,策划书范文案例,免费的招聘网站Leetcode647#xff1a;
问题描述#xff1a;
给你一个字符串 s #xff0c;请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。 示例 1#xff1a;
输入#xff1a;s
问题描述
给你一个字符串 s 请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。 示例 1
输入s abc
输出3
解释三个回文子串: a, b, c示例 2
输入s aaa
输出6
解释6个回文子串: a, a, a, aa, aa, aaa 提示
1 s.length 1000s 由小写英文字母组成
代码及注释
class Solution {
public:int countSubstrings(string s) {//枚举所有的连续子串int ns.size();int ans0;for(int i0;in;i){for(int ji;jn;j){if(iskey(s,i,j))ans;}}return ans;}bool iskey(string s,int i,int j){while(ij){if(s[i]!s[j])return false;i;j--;}return true;}
};
Leetcode516
问题描述
给你一个字符串 s 找出其中最长的回文子序列并返回该序列的长度。
子序列定义为不改变剩余字符顺序的情况下删除某些字符或者不删除任何字符形成的一个序列。 示例 1
输入s bbbab
输出4
解释一个可能的最长回文子序列为 bbbb 。示例 2
输入s cbbd
输出2
解释一个可能的最长回文子序列为 bb 。提示
1 s.length 1000s 仅由小写英文字母组成
代码及注释
class Solution {
public://dp[i][j]代表 s[i,j]最长回文子序列的长度// s[i]s[j] dp[i][j]dp[i1][j-1]2;// s[i]!s[j] dp[i][j]max(dp[i1][j],dp[i][j-1])int dp[1005][1005];int longestPalindromeSubseq(string s) {int ns.size();for(int in-1;i0;i--){dp[i][i]1;for(int ji1;jn;j){if(s[i]s[j]){dp[i][j]dp[i1][j-1]2;}else{dp[i][j]max(dp[i1][j],dp[i][j-1]);}}}return dp[0][n-1];}
};
