代码随想录算法训练营第57天 | 647、516网站首页 学无止境

代码随想录算法训练营第57天 | 647、516

somethingstrange 2024-07-14 06:01:02

简介代码随想录算法训练营第57天 | 647、516

647. 回文子串

题目描述

给你一个字符串 s ，请你统计并返回这个字符串中回文子串的数目。
回文字符串是正着读和倒过来读一样的字符串。
子字符串是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例1：
输入： $s = " ab c "$
输出： $3$
示例2：
输入： $s = " aaa "$
输出： $6$

思路

1、确定dp数组
dp[i][j]表示区间范围[i,j]的字串是否是回文子串，若是则为true，否则为false
2、确定递推公式
s[i]和s[j]不相等时，dp为false
若相等：
1）下标i与j相同，同一个字符例如a，肯定是回文子串
2）下标i与j相差为1，例如aa，也是回文子串
3）下标i与j相差大于1，例如cabac，此时只需看i+1，j-1的位置是否为true即可。
除了动态规划，本题也可以使用双指针，首先找到中心，然后向左右扩散以判断是否为回文串。

解法1

class Solution {
    public int countSubstrings(String s) {
        int ans = 0;
        int len = s.length();
        if(s == null || len < 1){
            return 0;
        }
        boolean[][] dp = new boolean[len][len];
        for(int j = 0;j<len;j++){
            for(int i = 0;i<=j;i++){
                if(s.charAt(i) == s.charAt(j)){
                    if(j-i < 3){
                        dp[i][j] = true;
                    }
                    else{
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                else{
                    dp[i][j] = false;
                }
            }
        }
        for(int i = 0;i<len;i++){
            for(int j = 0;j < len;j++){
                if(dp[i][j]){
                    ans++;
                }
            }
        }
        return ans;
    }
}

解法2

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;
    }
}

解法3

class Solution {
    public int countSubstrings(String s) {
        int len = s.length();
        int ans = 0;
        if(s == null || len< 1){
            return 0;
        }
        for(int i = 0; i < 2*len-1;i++){
            int left = i/2,right = left + i%2;
            while(left >= 0 && right < len && s.charAt(left) == s.charAt(right)){
                ans++;
                left--;
                right++;
            }
        }
        return ans;
    }
}

总结

本题难点在于，确定dp数组，很容易就会想到以i-1结尾的字符串的回文串长度，就没写出来了。

516. 最长回文子序列

题目描述

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例1：
输入： $s = " bbbab "$
输出： $4$
示例2：
输入： $s = " c bb d "$
输出： $2$

思路

与上一题相比，回文串换成了回文序列，也就是对元素的相连没有了要求，需要考虑的情况反而少了一些。
1、确定dp数组
dp[i][j]表示字符串s在[i,j]范围内最长的回文子序列的长度为dp[i][j]
2、确定递推公式
若s[i]和s[j]相同，那么dp[i][j] = dp[i+1][j-1]+2
若不相同，则分别加入s[i]、s[j]看那个可以组成最长的回文子序列

解法

class Solution {
    public int longestPalindromeSubseq(String s) {
        int len = s.length();
        int[][] dp = new int[len+1][len+1];
        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],Math.max(dp[i][j],dp[i][j-1]));
                }
            }
        }
        return dp[0][len-1];
    }
}