力扣657题：回文字串_给定一个字符串s,请输出这个字符串中回文子串的数目。 回文字符串是正着读和倒过

力扣657题：回文字串

题目描述

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

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

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

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

输入输出样例

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

输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
1
2
3

Tips

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

解法一：动态规划

//定义判断回文字串函数
    int countSubstrings(string s)
    {
        int length=s.size();

        //建立动态规划数组
        vector<vector<int>>dp(length,vector<int>(length));

        //统计状态转移方程中1的数目
        int count=0;
        //由于对角线的元素一定是回文，初始化对角线元素
        for(int i=0;i<length;i++)
        {
            dp[i][i]=1;
            count++;
        }


        //建立动态转移方程
        //从字串的长度中，到字符串长度不断增加
        for(int sublength=2;sublength<=length;sublength++)
        {
            //从字符串左边进行枚举
            //i为字符字串的左端点

            for(int i=0;i<length;i++)
            {
                //j为字符字串，作为字符串的右端点
                int j=i+sublength-1;

                if(j>=length)
                {
                    break;
                }

                //判断左端点和右端点是否相等
                if(s[i]!=s[j])
                {
                    dp[i][j]=0;
                }
                else{
                    //当字符串的长度在1，2，3只要两个端点两边相等就一定是回文字串
                    if(j-i+1<4)
                    {
                        dp[i][j]=1;
                        count++;
                    }
                    else{
                        //dp[i+1][j-1]是指靠近两个端点内部的字串是否为回文字串
                        dp[i][j]=dp[i+1][j-1];
                        if(dp[i][j])
                        {
                            count++;
                        }
                    }
                }

            }
        }
        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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

解法二：中心扩散法

 //使用中心扩散法
    int countSubstrings2(string s)
    {
        int ans=0;

        //中心点有2*len-1,分别为len个单字符和len-1个双字符
        //中心点即left指针和right指针初始化指向的地方，可能是一个也可能是两个
        for(int center=0;center<2*s.size()-1;center++)
        {
            int left=center/2;
            int right=left+center%2;
            while(left>=0&&right<s.size()&&s[left]==s[right])
            {
                ans++;
                //向两边进行扩散
                left--;
                right++;
            }
        }
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21