网站怎么广告投放,婚礼工作室网站模板,哈尔滨建设工程信息网查询系统,视频做网站文章目录 647. 回文子串516.最长回文子序列 647. 回文子串 力扣题目链接 代码随想录讲解 题意#xff1a;给你一个字符串 s #xff0c;请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的… 文章目录 647. 回文子串516.最长回文子序列 647. 回文子串 力扣题目链接 代码随想录讲解 题意给你一个字符串 s 请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。 具有不同开始位置或结束位置的子串即使是由相同的字符组成也会被视作不同的子串。 示例 1输入s abc输出3解释三个回文子串: a, b, c示例 2输入s aaa输出6解释6个回文子串: a, a, a, aa, aa, aaa思路见代码
class Solution {public int countSubstrings(String s) {char[] chars s.toCharArray();//代表[i,j]范围内的子串是否是回文子串如果是则为trueboolean[][] dp new boolean[chars.length][chars.length];//记录回文子串的长度int res 0;//根据递归公式看遍历顺序递归公式中由dp[i1][j-1]推出dp[i][j],是从左下角推过来的。所以遍历顺序要从下到上从左到右for(int i chars.length-1; i 0; i--) {for(int j i; j chars.length; j) {//如果字符i和j一样看i和j之间的子串是不是回文子串if(chars[i] chars[j]) {//如果j和i之间的距离小于等于1即a/aa这种情况一个单独的字符或两个相等元素的字符这样的子串是回文子串resif(j-i 1) {res;dp[i][j] true;} //当i和j之间的距离大于1时看i和j之间的子串是否是回文子串即看dp[i1][j-1]如果是那么i和j相同i到j也是回文。else if(dp[i1][j-1]) {res;dp[i][j] true;}} }}return res;}
}516.最长回文子序列 力扣题目链接 代码随想录链接 题意给你一个字符串 s 找出其中最长的回文子序列并返回该序列的长度。 子序列定义为不改变剩余字符顺序的情况下删除某些字符或者不删除任何字符形成的一个序列。 示例 1输入s bbbab输出4解释一个可能的最长回文子序列为 bbbb 。示例 2输入s cbbd输出2解释一个可能的最长回文子序列为 bb 。此题求回文子序列可以不连续。跟回文子串不一样回文子串要求必须连续。 思路见代码
class Solution {public int longestPalindromeSubseq(String s) {char[] chars s.toCharArray();int res 1;//代表在ij范围内最长的回文子序列的长度int[][] dp new int[chars.length][chars.length];for(int i 0; i chars.length; i) {dp[i][i] 1;}for(int i chars.length-1; i 0; i--) {for(int j i1; j chars.length; j) {if(chars[i] chars[j]) {dp[i][j] dp[i1][j-1] 2;} else {dp[i][j] Math.max(Math.max(dp[i1][j], dp[i][j-1]),dp[i][j]);}}}return dp[0][chars.length-1];}
}
