建设银行长春网站,上海网站开发企业,淘宝客推广网站源码,thinkphp做双语网站文章目录前言一、回文子串#xff08;力扣647#xff09;二、最长回文子序列#xff08;力扣516#xff09;前言
1、回文子串 2、最长回文子序列 一、回文子串#xff08;力扣647#xff09;
给你一个字符串 s #xff0c;请你统计并返回这个字符串中 回文子串 的数目…
文章目录前言一、回文子串力扣647二、最长回文子序列力扣516前言
1、回文子串 2、最长回文子序列 一、回文子串力扣647
给你一个字符串 s 请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串即使是由相同的字符组成也会被视作不同的子串 分析 1、确定dp[]数组以及下标含义
布尔类型的dp[i][j]表示区间范围[i,j] 注意是左闭右闭的子串是否是回文子串如果是dp[i][j]为true否则为false。
2、递推公式 分析两种情况 s[i]与s[j]相等s[i]与s[j]不相等两种 当s[i]与s[j]不相等那没啥好说的了dp[i][j]一定是false。 当s[i]与s[j]相等时 情况一下标i 与 j相同同一个字符例如a当然是回文子串 情况二i和j仅相差1“aa” 这样子 情况三i-j1 “abccba” 或者 “abca”此时我们需要判断i-1 和 j1是不是回文子串 3、初始化 都初始为false 4、遍历顺序 从下到上
class Solution {public int countSubstrings(String s) {int res 0;char[] ss s.toCharArray();if (s null || (s.length() 1)) return 0;boolean[][] dp new boolean[ss.length][ss.length];for(int is.length()-1;i0;i--){for(int ji;js.length();j){if(ss[i]ss[j]){if(Math.abs(i-j)1){dp[i][j] true;res;}else if(dp[i1][j-1]true){dp[i][j] true;res;}}else{dp[i][j] false;}}}return res;}
}二、最长回文子序列力扣516
给你一个字符串 s 找出其中最长的回文子序列并返回该序列的长度。
子序列定义为不改变剩余字符顺序的情况下删除某些字符或者不删除任何字符形成的一个序列。 分析
回文子串是要连续的回文子序列可不是连续的 思路其实是差不多的但本题要比求回文子串简单一点因为情况少了一点。 1、确定dp数组以及下标含义 dp[i][j]表示区间范围[i,j] 注意是左闭右闭的子串回文子串的长度最大为dp[i][j]
2、递推公式 分析两种情况 如果s[i]与s[j]不相同说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子序列的长度那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。
加入s[j]的回文子序列长度为dp[i 1][j]。 加入s[i]的回文子序列长度为dp[i][j - 1]。
那么dp[i][j]一定是取最大的即dp[i][j] max(dp[i 1][j], dp[i][j - 1]);
当s[i]与s[j]相等时 dp[i][j] dp[i1][j-1] 2;
3、初始化 在对角线上的情况dp[i][j]应该是初始为1的。即一个字符的回文子序列长度就是1。 其他情况dp[i][j]初始为0就行 4、遍历顺序 从下到上
class Solution {public int longestPalindromeSubseq(String s) {int[][] dp new int[s.length()][s.length()];if(snull || s.length()0) return 0;//初始化for(int i0;is.length();i){dp[i][i] 1;}//遍历顺序for(int is.length()-2;i0;i--){for(int ji1;js.length();j){if(s.charAt(i)s.charAt(j)){dp[i][j] dp[i1][j-1]2;}else{dp[i][j] Math.max(dp[i][j-1],dp[i1][j]);}}}return dp[0][s.length()-1];}
}
