回文子串-动态规划_回文子串动态规划

• 题目

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

• 示例

输入：s = “abc”
输出：3

• 算法

dp[i][j]表示s[i…j]是否是回文串
只有但s[i]==s[j]时，才有可能是回文串
如果i+1 >= j-1,则不需要看dp[i+1][j-1]是否是回文串
否则，要看dp[i+1][j-1]是否是回文串

• 代码

public int countSubstrings(String s) {
        int n = s.length();
        int count = 0;
        boolean[][] dp = new boolean[n][n];
        for (int i = n-1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (j-1 <= i+1) {
                        dp[i][j] = true;
                        count++;
                    } else {
                        if (dp[i+1][j-1]) {
                            dp[i][j] = true;
                            count++;
                        }
                    }
                }
            }
        }
        return count;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• 算法

遍历子串中心点，分奇数和偶数两种情况
j表示半径，不断扩大半径判断是否相等，如果不相等，则半径再扩大也不会是回文串

• 代码

public int countSubstrings(String s) {
        int n = s.length();
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; i - j >= 0 && i + j < n; j++) {
                if (s.charAt(i - j) == s.charAt(i + j)) {
                    res++;
                }else {
                    break;
                }
            }
            for (int j = 1; i - j + 1 >= 0 && i + j < n; j++) {
                if (s.charAt(i - j + 1) == s.charAt(i + j)) {
                    res++;
                } else {
                    break;
                }
            }
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21