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

一、647. 回文子串

注意的点：

1. dp含义：i-j的子串是否是回文子串（j>=i） ——> 因此，只需要考虑斜对角线上半部分
2. 由于当前格子依赖左下角格子[i+1][j-1]，所以遍历顺序：从下到上，从左到右
3. 如果只是一个或两个字符，则是回文子串；有三个以上字符，但是两边字符中间的子串是回文串，则也是回文串

以下是代码部分：

public class 回文子串647 {

    public int countSubstrings(String s) {

        int result = 0;

        //dp含义：i-j的子串是否是回文子串（j>=i） ——> 因此，只需要考虑斜对角线上半部分
        boolean[][] dp = new boolean[s.length()][s.length()];

        //初始化：全为false

        //遍历
        //由于当前格子依赖左下角格子[i+1][j-1]，所以遍历顺序：从下到上，从左到右
        for (int i = s.length()-1; i >= 0; i--) {
            for (int j = i; j < s.length(); j++) {

                //两种情况：相等和不等
                if(s.charAt(i) == s.charAt(j)){

                    //如果只是一个或两个字符，则是回文子串
                    if(i == j || i+1 == j){
                        dp[i][j] = true;
                        result++;
                    }

                    //有三个以上字符，但是两边字符中间的子串是回文串，则也是回文串
                    else if(dp[i+1][j-1]){
                        dp[i][j] = true;
                        result++;
                    }
                }
            }
        }

        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

二、516.最长回文子序列

1. dp含义：存储i-j子串中最长的回文子序列
2. 初始化:由于是从下往上遍历，所以初始化最右下角的值。同时，斜对角线的下半部分全部初始化为0，斜对角初始化为1
3. 如果两个值相等，则就是左下角的值 + 2(多了i、j两个字符)，否则，就取仅包含i或者j的最大值

以下是代码部分：

public class 最长回文子序列516 {

    public int longestPalindromeSubseq(String s) {

        //dp含义：存储i-j子串中最长的回文子序列
        int[][] dp = new int[s.length()][s.length()];

        //初始化:由于是从下往上遍历，所以初始化最右下角的值。
        //同时，斜对角线的下半部分全部初始化为0
        //dp[s.length()-1][s.length()-1] = 1;

        for (int i = s.length()-1; i >= 0; i--) {
            for (int j = i; j < s.length(); j++) {

                //额外加一个单个字符的判断，防止在dp[0][0]处越界
                //其实这里也相当于初始化
                if(i == j){
                    dp[i][j] = 1;
                    continue;
                }

                //如果两个值相等，则就是左下角的值 + 2(多了i、j两个字符)
                if(s.charAt(i) == s.charAt(j))
                    dp[i][j] = dp[i+1][j-1] + 2;

                //否则，就取仅包含i或者j的最大值
                else
                    dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j]);
            }
        }

        return dp[0][s.length()-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34