【LeetCode】647. 回文子串

题目描述

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

示例 1：

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

示例 2：

输入：s = “aaa”
输出：6
解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

提示：

1 <= s.length <= 1000
s 由小写英文字母组成

方法一：动态规划

class Solution {
public:
    int countSubstrings(string s) {
        int length = s.length();
        int result = 0; //回文子串的数量
        vector<vector<bool>> dp(length, vector<bool>(length, false));
        // 对应于第三种情况 dp[i][j] = dp[i+1][j-1]
        // 因此需要从下往上、从左往右遍历
        // 矩阵下三角和上三角是对称，所以j从j=i开始，只考虑上三角
        for(int i=length-1; i>=0; i--){
            for(int j=i; j<length; j++){
                if(s[i] == s[j]){
                    // i=j和i+1==j两种情况
                    // 分别对应a 和 aa
                    if(i+1 >= j){
                        dp[i][j] =true;
                        // 直接用result记录
                        result++;
                    }  
                    // i+1 < j的情况，如cbabc
                    // 此时是否是回文取决于bab
                    else if(dp[i+1][j-1]){
                        dp[i][j] = dp[i+1][j-1];
                        result++;
                    }
                }
                else dp[i][j] = false;
            }
        }
        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

方法二：中心拓展法/双指针法

class Solution {
public:
    int countSubstrings(string s) {
        int length = s.length();
        int result = 0; //回文子串的数量
        for(int i=0; i<length; i++){
            result += extend(s, i, i, length); // 一个中心
            result += extend(s, i, i+1, length); // 两个中心
        } 
        return result;
    }
    int extend(const string& s, int i, int j, int n){
        int res=0;
        while(i>=0 && j<=n && s[i]==s[j]){
            i--;
            j++;
            res++;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

心得

• 本科的时候应该就有做过回文子串的题目，当初就不太会，因此想了一会就看了题解，果然我脑子里出现的又是暴力解法，看了题解的动态规划，豁然开朗。
• 方法一：动态规划

1. 确定dp数组（dp table）以及下标的含义
   布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。
2. 确定递推公式，有以下两大种情况：

• s[i] = s[j] ，其中对于 i 和 j 的讨论又可以细分为三种情况：
  i == j：True，如’a’
  i+1 ==j ：True ，如’aa’
  i+1 > j： dp[i][j] = dp[i+1][j-1] ,如’cbabc’，当 i 和 j 分别指向首尾的c时，此时这个子串是否是回文子串取决于’bab’是否是回文子串。
• s[i] != s[j]：False

3. dp[i][j] 初始化 为false
4. 确定遍历顺序，从递推公式可以看出，dp[i][j] 取决于 dp[i+1][j-1]，如图所示，后者位于前者的左下角，因此对于dp数组，需要从下往上、从左往右依次遍历
   
5. 举例推导dp数组，会发现dp数组的上三角和下三角是完全对称的，因此只需要计算dp数组的上三角，即令 j=i 开始遍历。

• 时间复杂度：O(n²)
  空间复杂度：O(n²)

• 方法二：中心拓展法/双指针法
  动态规划的空间复杂度比较高，本方法的空间复杂度仅为O(1)
• 思路： 首先确定中心字符串，然后向左右两边扩展，判断是否对称。
  在选择中心点的时候，要注意中心点有两种情况：一个元素可以作为中心点，两个元素也可以作为中心点。之后，三个元素就可以由一个元素左右扩展1位得到。
• 时间复杂度：O(n²)
  空间复杂度：O(1)

参考题解：647. 回文子串