Day 51 || 647. 回文子串、516.最长回文子序列

647. 回文子串

题目链接：力扣题目链接

思路：这个需要想到如果两个对比位置小于等于一时候只要相等就成立，但是要是大于一时候就需要判断两者之间是否成立，比如i-j大于1，那么i+1到j-1就应该要成立那么i到j才能成立。因为要判断dp[i + 1][j - 1]是否成立，这个是从左下计算的，所以可以知道这个dp中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()-1;j++){
                if(s.charAt(i)==s.charAt(j)){
                    if (j - i <= 1 || dp[i + 1][j - 1]) {
                        dp[i][j] = true;
                        res++;
                    }
                }
            }
        }
        return res;
    }
}

还有一个双指针思路

class Solution {
    public int countSubstrings(String s) {
        int len, ans = 0;
        if (s == null || (len = s.length()) < 1) return 0;
        //总共有2 * len - 1个中心点
        for (int i = 0; i < 2 * len - 1; i++) {
            //通过遍历每个回文中心，向两边扩散，并判断是否回文字串
            //有两种情况，left == right，right = left + 1，这两种回文中心是不一样的
            int left = i / 2, right = left + i % 2;
            while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {
                //如果当前是一个回文串，则记录数量
                ans++;
                left--;
                right++;
            }
        }
        return ans;
    }
}

516.最长回文子序列

class Solution {
    public int longestPalindromeSubseq(String s) {
        int[][] dp = new int[s.length()][s.length()];
        int res = 0;
         for(int j=0;j<s.length();j++){
            dp[j][j] = 1;
         }
        for(int i=s.length()-1;i>=0;i--){
            for(int j=i;j<=s.length()-1;j++){
                if(s.charAt(i)==s.charAt(j)){
                    if(j-i>=1){
                        dp[i][j] = dp[i + 1][j - 1] +2;  
                    }                   
                }else{
                    dp[i][j] = Math.max(dp[i][j - 1],dp[i + 1][j]);
                }
            }
        }
        return dp[0][s.length()-1];
    }
}