seo网站建设,高端装饰设计公司名称,接网站建设单子的网站,公司单页设计力扣647.回文子串
题目链接#xff1a;https://leetcode.cn/problems/palindromic-substrings/
思路
dp数组含义
dp[i][j]:以s[i]为开头#xff0c;s[j]为结尾的子串是否是回文子串
递推公式
子串范围为[i,j]#xff0c;当s[i]s[j]时#xff0c;有三种情况#xff1…力扣647.回文子串
题目链接https://leetcode.cn/problems/palindromic-substrings/
思路
dp数组含义
dp[i][j]:以s[i]为开头s[j]为结尾的子串是否是回文子串
递推公式
子串范围为[i,j]当s[i]s[j]时有三种情况
1ij,如[a]dp[i][j]true同时计数器res;
2ji1,如[a,a]dp[i][j]true同时计数器res;
3j-i1那么就需要判断子串内部即[i1,j-1]范围内是否是回文子串如果是则dp[i][j]true否则为false。
初始化
初始化为false
遍历顺序
由递推公式可知,dp[i][j]由dp[i1][j-1]推导而来所以要从底往上从左到右遍历。
打印数组
返回计数器res。
完整代码
class Solution {public int countSubstrings(String s) {boolean[][] dp new boolean[s.length()][s.length()];int res 0;for (int i s.length()-1; i 0; i--) {for (int j i; j s.length(); j) {if(s.charAt(i) s.charAt(j)){if(j - i 1) {dp[i][j] true;res;}else if (dp[i1][j-1] true){dp[i][j] true;res;}}}}return res;}
}力扣516.最长回文子序列
题目链接https://leetcode.cn/problems/longest-palindromic-subsequence/
思路
本题和回文子串的区别是子序列是不要求连续的可以删除字符
dp数组含义
dp[i][j]:在[i,j]范围内的最长回文子序列的长度
递推公式
1s[i]s[j]时dp[i][j] dp[i1][j-1]2这个很好理解2是加上两端的字符
2s[i]!s[j]时说明两端字符同时加进去时不能构成回文字符串所以考虑两种情况1.放左边的不放边的dp[i][j]dp[i][j-1];2.放右边的不放左边的dp[i][j]dp[i1][j]。取二者最大值
初始化
由递推公式dp[i][j] dp[i1][j-1]2可知,i和j不能相等。所以初始化时ij即一个字符串的回文长度为1.其余为0
遍历顺序
和回文子串同理
打印数组
根据dp数组的含义返回dp[0][s.length()-1]
完整代码
class Solution {public int longestPalindromeSubseq(String s) {int[][] dp new int[s.length()][s.length()];for (int i 0; i s.length(); i) {dp[i][i] 1;}for (int i s.length()-1; i 0; i--) {for (int j i1; j s.length(); j) {if (s.charAt(i) s.charAt(j)){dp[i][j] dp[i1][j-1]2;}else {dp[i][j] Math.max(dp[i1][j],dp[i][j-1]);}}}return dp[0][s.length()-1];}
}
