力扣647.回文子串

題目鏈接：https://leetcode.cn/problems/palindromic-substrings/

思路

dp數(shù)組含義

dp[i][j]:以s[i]為開頭，s[j]為結(jié)尾的子串是否是回文子串

遞推公式

子串范圍為[i,j]，當s[i]==s[j]時，有三種情況：

（1）i==j,如[a]，dp[i][j]=true，同時計數(shù)器res++;

（2）j=i+1,如[a,a]，dp[i][j]=true，同時計數(shù)器res++;

（3）j-i>1，那么就需要判斷子串內(nèi)部，即[i+1,j-1]范圍內(nèi)是否是回文子串，如果是，則dp[i][j]=true；否則為false。

初始化

初始化為false

遍歷順序

由遞推公式可知,dp[i][j]由dp[i+1][j-1]推導而來，所以要從底往上，從左到右遍歷。

打印數(shù)組

返回計數(shù)器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[i+1][j-1] == true){dp[i][j] = true;res++;}}}}return res;}
}

力扣516.最長回文子序列

題目鏈接：https://leetcode.cn/problems/longest-palindromic-subsequence/

思路

本題和回文子串的區(qū)別是：子序列是不要求連續(xù)的，可以刪除字符！

dp數(shù)組含義

dp[i][j]:在[i,j]范圍內(nèi)的最長回文子序列的長度

遞推公式

（1）s[i]==s[j]時，dp[i][j] = dp[i+1][j-1]+2，這個很好理解，+2是加上兩端的字符

（2）s[i]!=s[j]時，說明兩端字符同時加進去時不能構(gòu)成回文字符串，所以考慮兩種情況：1.放左邊的，不放邊的：dp[i][j]=dp[i][j-1];2.放右邊的，不放左邊的：dp[i][j]=dp[i+1][j]。取二者最大值

初始化

由遞推公式dp[i][j] = dp[i+1][j-1]+2可知,i和j不能相等。所以初始化時，i=j即一個字符串的回文長度為1.其余為0

遍歷順序

和回文子串同理

打印數(shù)組

根據(jù)dp數(shù)組的含義，返回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 = i+1; j < s.length(); 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][s.length()-1];}
}