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

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

一、647. 回文子串

题目链接：https://leetcode.cn/problems/palindromic-substrings/
思路：回文子串类似于abcba这种，定义dp[i][j]表示左闭右闭区间s[i,j]是否为回文子串。
当s[i]=s[j] 时那么dp[i][j]一定是false。
当s[i] == s[j] 时分为两种情况：
情况一：j-i<=1，说明要不是i==j就是同一个位置，单个元素当然是回文子串。
要不就是s[i]和s[j]紧挨着，前面的条件是s[i]==s[j]，那么两个相等的紧挨着的元素当然也是回文子串
情况二：j-1>1时，此时s[i]和s[j]之间最起码搁着一个元素，那么dp[i][j]是否是回文子串就依赖于s[i+1][j-1]是否是回文子串。
此时若dp[i+1][j-1]=true那么dp[i][j]便是回文子串。

如何初始化：前面推导发现dp[i][j]依赖于dp[i+1][j-1]那么一定要从下往上，从左往右遍历。
此外，定时dp时，是区间s[i,j]那么一定是j>=i的。

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) && (j - i <= 1 || dp[i + 1][j - 1])) {
                    res++;
                    dp[i][j] = true;
                }
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

二、516.最长回文子序列

题目链接：https://leetcode.cn/problems/longest-palindromic-subsequence/
思路：定义dp[i][j]表示区间[i,j]中的最长回文子序列为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];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19