Leetcode647.回文子串_尽可能多的回文子串

题目

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。
示例 1:

输入: “abc”
输出: 3
解释: 三个回文子串: “a”, “b”, “c”.

示例 2:

输入: “aaa”
输出: 6
说明: 6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”.

注意:

• 输入的字符串长度不会超过1000。

思路一

该题是最长回文字符串的变体。在最长回文字符串中，利用中心扩展法先求解回文串，再比较该串长度与已保存的长度，决定是否更新。因此本题也可以利用中心扩展法，当求出一个回文字符串时count++,返回以该字符或者该字符与其相邻字符为中心的所有回文串数量，并累加。
时间复杂度：O（N²)

class Solution {
    public int countSubstrings(String s) {
        //定义结果变量;
        int ret = 0;
        int len = s.length();
        //Step2:判断特殊情况
        if(len < 2) return len;
        for(int i = 0; i < len; i++){
            ret += expand(s, i, i);
            ret += expand(s, i, i+1);
        }
        //Step3:返回结果变量
        return ret;
    }
    private int expand(String s, int left, int right){
        int L = left, R = right;
        int count = 0;
        while(L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)){
            count++;
            L--; R++;
        }
        
        return count;
    }
}
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

思路二

采用动态规划的方法，关键点：

1. 初始化：dp[i][i] = true;
2. 状态转移方程：对于S（i……j），
   • 如果s.charAt(i) == s.charAt(j)为真，需要继续判断两种情况：如果 j - i < 3,则这两个字符相邻或者这两个字符之间存在一个字符，dp[i][j] = true; 否则dp[i][j] = dp[i+1][j-1];
   • 如果s.charAt(i) == s.charAt(j)为假，则dp[i][j] = false
3. 结果变量的变化，每次计算出dp[i][j]值时，若为真，则ret++,否则不变。

class Solution {
    public int countSubstrings(String s) {
        //Step1:定义结果变量;
        int ret = 0;
        int len = s.length();
          //Step2:判断特殊情况
        if(len < 2) return len;
        //动态规划的辅助变量
        boolean[][] dp = new boolean[len][len];
        //初始化
        for(int i = 0; i < len;  i++)dp[i][i] = true;
        ret = len;

        for(int j = 1; 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];
                    }
                }

                if(dp[i][j]) ret++;
            }
        }
        //Step3:返回结果变量
        return ret;
    }
}
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