代码随想录算法训练营第五十二天 | 647. 回文子串、516.最长回文子序列、动态规划总结篇、复习

647. 回文子串

题目链接：https://leetcode.cn/problems/palindromic-substrings/
文档讲解：https://programmercarl.com/0647.%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2.html
视频讲解：https://www.bilibili.com/video/BV17G4y1y7z9/

思路

• 确定dp数组以及下标的含义：
• 确定递推公式：当s[i] == s[j]时，
  • 情况一：i == j，比如a。递推公式为dp[i][j] = true；
  • 情况二：j - i < 1，比如aa。递推公式为dp[i][j] = true；
  • 情况三：j - i > 1。递推公式为if (dp[i + 1][j - 1] == true) dp[i][j] = true；
• dp数组如何初始化：初始化为false。
• 确定遍历顺序：从左下到右上。所以i从最大值开始递减，由于j大于等于i，所以j从i开始递增。
• 打印dp数组，用于debug

代码

class Solution {
    public int countSubstrings(String s) {
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        for (boolean[] row : dp)  Arrays.fill(row, false);
        int res = 0;
        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) {
                        dp[i][j] = true;
                        res++;
                    } else {
                        if (dp[i + 1][j - 1] == true) {
                            dp[i][j] = true;
                            res++;
                        }
                    }
                }
            }
        }
        return res;
    }
}

分析：时间复杂度：O(n²)，空间复杂度：O(n²)。

516.最长回文子序列

题目链接：https://leetcode.cn/problems/longest-palindromic-subsequence/
文档讲解：https://programmercarl.com/0516.%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E5%BA%8F…
视频讲解：https://www.bilibili.com/video/BV1d8411K7W6/

思路

• 确定dp数组以及下标的含义：[i, j]子串最长回文子序列长度为dp[i][j]。
• 确定递推公式：
• dp数组如何初始化：左上到右下的对角线初始化成1。
• 确定遍历顺序：左下到右上。
• 打印dp数组，用于debug

代码

class Solution {
    public int longestPalindromeSubseq(String s) {
        int len = s.length();
        int[][] dp = new int[len][len];
        for (int i = len - 1; i >= 0; i--) {
            dp[i][i] = 1;// 初始化可以和递推合并到一个循环中
            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];
    }
}

分析：时间复杂度：O(n²)，空间复杂度：O(n²)。

动态规划部分总结

文档讲解：https://programmercarl.com/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E6%80%BB%E7%BB%93%E7%AF…

复习字符串

344.反转字符串
541. 反转字符串II
卡码网：54.替换数字