【Leetcode】647.回文子串

647 回文子串

题目

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：
输入："abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：
输入："aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

方法1（动态规划）

  • dp数组定义：dp[i][j]表示字符串s在[i,j]区间的子串是否是一个回文串
  • 状态转移方程：当s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1])时，dp[i][j] = true,否则为false。
1
2
3
4
5
6
7
8
9
10
11
12
13
public int countSubstrings(String s) {
    boolean[][] dp = new boolean[s.length()][s.length()];
    int res = 0;
    for (int j = 0; j < s.length(); j++) {
        for (int i = 0; i <= j; i++) {
            if(s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
                res++;
            }
        }
    }
    return res;
}

时间复杂度：$O(n^2)$
空间复杂度：$O(n^2)$

方法2（中心扩展法）

假设字符串的长度为N，那么回文串可能的中心有2N-1种。其中，每个单字符串都可作为回文串的中心，这种情况有N种。其次，双字符串也可作为回文串的中心，这种情况有N-1种。单字符中心负责扩展成长度为奇数的字符串，双字符串中心可以扩展成长度为偶数的字符串。例如：

  • 字符串“aba”有5种可能的中心：a、b、c、ab、ba
  • 字符串“abba”有7种可能的中心：a、b、b、a、ab、bb、ba

中心扩展法的基本思想为：对于每一个中心都计算一次以其为中心的回文串个数。

具体算法：对于每一个可能的回文中心，都尽可能地扩展它对应的回文区间[left, right]，直到left<0或者right>=N或者S[left] != S[right]为止

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int countSubstrings(String s) {
    int res = 0, N = s.length();
    for(int center = 0; center < 2N - 1; center++){
        //center为偶数时left和right指向同一个位置，center为奇数时right指向left的后一个位置
        int left = center / 2;
        int right = left + center % 2;
        while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
            res++;
            left--;
            right++;
        }
    }
    return res;
}

时间复杂度：$O(n^2)$（对于每一个可能的中心都要遍历一次字符串）
空间复杂度：O(1)

对于本题的中心扩展法稍加修改，可以解决5.最长回文子串