647.回文子串

🔄647.回文子串

给你一个字符串 s ,请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

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

示例

  • 示例 1:

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

  • 示例 2:

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

两个aa不一样的原因是因为结束位置不同,但是为什么只有两个aa,应该有三个aa?

  • 提示:

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

思路

基本思想

需要求出字符串的全部子串,然后判断每一个子串是不是回文串,也就是求出当前字符串的幂集,然后统计幂集中的所有回文子串的数目,不包括空集

所以得到了一下代码:

 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:
    vector<char> path;
    int res=0;
    int countSubstrings(string s) {
        backtrack(s,0);
        return res;
    }
    //回溯法求解字符串的幂集
    void backtrack(string s,int index){
        if(isCircle(path))//是回文串结果加一
            ++res;
        if(index==s.size())
            return;
        for(int i=index;i<s.size();++i){
            path.push_back(s[i]);
            backtrack(s,i+1);
            //回溯完成之后返回
            path.pop_back();
        }
    }
    //判断一个字符串是不是回文串
    bool isCircle(vector<char> s){
        if(s.size()==0)
            return false;
        for(int i=0,j=s.size()-1;i<j;++i,--j){
            if(s[i]!=s[j])
                return false;
        }
        return true;
    }
};

但是会出现问题,回溯法认为,aaa字符串会产生三个不同的aa,但是本题中认为只会产生两个不同的aa,按照题目要求确实应该产生三个不同的aa,不知道为什么。。。。


回溯法的办法行不通,于是考虑动态规划,此时动态规划由小到大的进行积累

其中dp[i][j]代表i~j区间的元素是否是回文串,可由更小的区间i+1~j-1确定,判断逻辑为:

1
2
3
if(s[i]==s[j]&&dp[i+1][j-1]){
    dp[i][j]=true;
}

当当前两个元素相等,并且更小范围的子串是回文串,那么当前子串也是回文串

由于当前的dp[i][j]dp[i+1][j-1]确定,相当于新的元素由左下角的元素确定,所以遍历的时候需要从左下角开始遍历,对应到图中为:

image-20230702200948694

判断回文时,有两种情况无法计算dp[i+1][j-1]

  1. i==j时,此时只有一个元素,所以一定是回文
  2. i+1==j时,此时有两个元素,在s[i]==s[j]的前提下,一定是回文串

这两种情况无法计算dp[i+1][j-1],所以单独处理

执行流程

  1. 初始化dp数组
  2. 从左下角开始遍历
  3. 一旦你出现一个回文串,结果数就+1
  4. 返回最终结果

代码

根据以上分析,得出以下代码:

 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
class Solution {
public:
    int countSubstrings(string s) {
        vector<vector<bool>> dp(s.size(),
                                vector<bool>(s.size(),false));
        int res=0;
        for(int i=s.size()-1;i>=0;--i){
            //为了从一个元素开始统计,j从i开始
            //搜索的范围就是主对角线的右半部分
            for(int j=i;j<s.size();++j){
                if(s[i]==s[j]){
                    //两种情况单独处理
                    if(i==j||i+1==j){
                        dp[i][j]=true;
                        res++;
                    }else if(dp[i+1][j-1]){
                        dp[i][j]=true;
                        res++;
                    }
                }
            }
        }
        return res;
    }
};

总结

主要是找到dp[i][j]dp[i+1][j-1]的关系

并且知道需要从左下角开始遍历,内层循环的起始位置从i开始,这样可以保证先从一个元素的情况进行统计

并且知道当i==j或者i+1==j时,需要单独处理