代码随想录算法训练营第五十七天| 647. 回文子串 516.最长回文子序列

代码随想录算法训练营第五十七天| 647. 回文子串 516.最长回文子序列

一、力扣647. 回文子串

题目链接
思路：对于字符串cabac，其中a,b,c,aba,cabac，都是回文子串，如果当前的字串是回文字串，那么它的字串中也会有回文字串，所以状态是有区间的，确定dp数组，dp[i][j]表示，区间[i,j]左闭右闭，表示该区间内的子串是否是回文子串。
当i=j时，一定是回文子串。
当s[i]=s[j]，且i+1=j时，是回文子串，类似aa。
当s[i]=s[j]，且i+2=j时，也就是类似于aba,i=0,j=2,只要中间的子串是回文子串，那么它也是，故只要dp[i+1][j-1]=true，即为回文子串。
遍历时要注意区间[i,j]（i<j），且从下向上，从左向右。

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[i+1][j-1]) {result++;dp[i][j] = true;}}}}return result;}
}

二、力扣 516.最长回文子序列

题目链接
思路：上面求回文子串数量，是连续的，这里求最长回文子串，是非连续的，依然是dp[i][j]区间[i,j]。
如果s[i]=s[j]那么，状态转移公式就出来了dp[i][j] = dp[i+1][j-1] + 2。
如果s[i]!=s[j]那么，就各取一个留最长的， dp[i][j] = Math.max(dp[i+1][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 = i+1; j < len; j++) {if (s.charAt(i) == s.charAt(j)) {dp[i][j] = dp[i+1][j-1] + 2;}else {dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);}}}return dp[0][len-1];}
}