滑县住房和城乡建设局网站,logo设计在线制作,宁波 住房和建设局网站,网站大全2021代码随想录算法训练营第五十七天| 647. 回文子串 516.最长回文子序列
一、力扣647. 回文子串
题目链接 思路#xff1a;对于字符串cabac#xff0c;其中a,b,c,aba,cabac#xff0c;都是回文子串#xff0c;如果当前的字串是回文字串#xff0c;那么它的字串中也会有回文…代码随想录算法训练营第五十七天| 647. 回文子串 516.最长回文子序列
一、力扣647. 回文子串
题目链接 思路对于字符串cabac其中a,b,c,aba,cabac都是回文子串如果当前的字串是回文字串那么它的字串中也会有回文字串所以状态是有区间的确定dp数组dp[i][j]表示区间[i,j]左闭右闭表示该区间内的子串是否是回文子串。 当ij时一定是回文子串。 当s[i]s[j]且i1j时是回文子串类似aa。 当s[i]s[j]且i2j时也就是类似于aba,i0,j2,只要中间的子串是回文子串那么它也是故只要dp[i1][j-1]true即为回文子串。 遍历时要注意区间[i,j]ij且从下向上从左向右。
class Solution {public int countSubstrings(String s) {int len s.length(), result 0;boolean[][] dp new boolean[len][len];for (int i len-1; i 0; i--) {for (int j i; j len; j) {if (s.charAt(i) s.charAt(j)) {if (j - i 1) {result;dp[i][j] true;}else if (dp[i1][j-1]) {result;dp[i][j] true;}}}}return result;}
}
二、力扣 516.最长回文子序列
题目链接 思路上面求回文子串数量是连续的这里求最长回文子串是非连续的依然是dp[i][j]区间[i,j]。 如果s[i]s[j]那么状态转移公式就出来了dp[i][j] dp[i1][j-1] 2。 如果s[i]!s[j]那么就各取一个留最长的 dp[i][j] Math.max(dp[i1][j], dp[i][j-1])。
class Solution {public int longestPalindromeSubseq(String s) {int len s.length();int[][] dp new int[len][len];for (int i 0; i len; i) {dp[i][i] 1;}for (int i len-1; i 0; i--) {for (int j i1; j len; 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][len-1];}
}
