算法刷题｜647.回文子串、516.最长回文子序列-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法刷题｜647.回文子串、516.最长回文子序列。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

回文子串

题目：给你一个字符串 s ，请你统计并返回这个字符串中回文子串的数目。

回文字符串是正着读和倒过来读一样的字符串。

子字符串是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

dp[i][j] 表示[i,j]范围内的字符串是否是回文字符串
递推公式：判断s.charAt(i) 和 s.charAt(j)是否相等
- 相等：如果i==j，说明只有一个字符，肯定是回文，例如a；如果j-1 = i，说明只有两个字符，并且相等，也肯定是回文，例如aa；如果j-1>i，这时候就需要判断i+1到j-1的范围是否是回文了
- 不相等：那肯定就不是了
dp数组初始化：默认全是false
遍历顺序：我们的dp[i][j]主要是由于dp[i+1][j-1]推导出来的，所有我们应该先从大到小遍历i，然后从小到大遍历j
打印dp数组

class Solution {
    public int countSubstrings(String s) {
        // dp[i][j] 表示[i,j]范围内的字符串是否是回文字符串
        boolean[][] dp = new boolean[s.length()][s.length()];
        // 初始化 dp[i][j] = false;
        // 记录结果
        int res = 0;
        for(int i = s.length()-1;i>=0;i--){
            for(int j = i;j<s.length();j++){// 根据dp定义知道j是大于i的所以这里j至少需要从i开始
                if(s.charAt(i) == s.charAt(j)){
                    if(j-i<=1){
                        dp[i][j] = true;
                        res++;
                    }else{
                        if(dp[i+1][j-1]){
                            dp[i][j] = true;
                            res++;
                        }
                    }
                }
            }
        }
        return res;
    }
}

最长回文子序列

题目：给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

思路：本题和上一题的最大的区别在于，上一题求的是子字符串（必须连续），本题是子序列（可以不连续）文章来源地址https://www.toymoban.com/news/detail-580383.html

dp[i][j]表示[i,j]范围内的字符串中最长回文子序列的最大长度为dp[i][j]
递推公式：s.charAt(i) 和 s.charAt(j)是否相等
- 相等：dp[i][j] = dp[i+1][j-1] + 2;因为是左右两个字符，所有加2
- 不相等：dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
  - 保留j位置字符：dp[i+1][j]
  - 保留i位置字符：dp[i][j-1]
dp初始化： dp[i][i] = 1，因为当i=j的时候就是只有一个字符，一个字符也是回文子序列，长度为1
遍历顺序：本题和上题一样
打印dp

class Solution {
    public int longestPalindromeSubseq(String s) {
        // dp[i][j]表示[i,j]范围内的字符串中最长回文子序列的最大长度为dp[i][j]
        int[][] dp = new int[s.length()][s.length()];
        // 初始化 dp[i][i] = 1
        for(int i = 0;i<s.length();i++){
            dp[i][i] = 1;
        }
        for(int i = s.length()-1;i>=0;i--){
            // 为什么j从i+1开始，因为j=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+1][j] 保留j位置的字符
                    // dp[i][j-1] 保留i位置的字符
                    dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return dp[0][s.length()-1];
    }
}