LeetCode第 647 题：回文子串(C++)_leetcode 647 c++

647. 回文子串 - 力扣（LeetCode）

类似题：LeetCode第 5 题：最长回文子串(C++)_zj-CSDN博客

中心扩散法

本题我们要统计的是个数，需要对上述代码稍作修改：

class Solution {
public:
    int countSubstrings(string s) {
        int res = 0;
        int left = 0, right = 0;
        for(int i = 0; i < s.size(); ++i){
            left = right = i;//初始left,right都指向中心位置
            while(right < s.size()-1 && s[right] == s[right+1]){//处理叠词的情况
                ++right;
                ++res;
            }
            while(right < s.size() && left >= 0 && s[right] == s[left]){//中心扩散
                ++res;
                ++right;//往右
                --left;//往左
            }
        }
        return  res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

中心扩散法改进

看了官方题解回文子串 - 回文子串 - 力扣（LeetCode）只有，发现可以进行优化如下：

上面的方法第一个while循环用于检查叠词的情况，因为叠词的时候回文子串可能是偶数长度的。换句话说，如果一个回文子串长度是偶数的，比如 “abccba”，我们怎么在它身上使用中心扩散法呢？

上面的方法是特殊处理叠词的情况，让left指向第一个 ‘c’，right指向第二个 ‘c’。那这种特殊处理是否可以转化为一般情况呢？直接定位一个中心，然后向两边扩散？

那可以只使用一次while循环吗？不难看出回文长度为奇数的时候，回文中心是一个字符；回文长度为偶数的时候，回文中心是两个字符。下面内容来自题解：

这个题解也讲的很清晰：两道回文子串的解法（详解中心扩展法） - 回文子串 - 力扣（LeetCode）

所以可以对奇偶进行统一处理：

class Solution {
public:
    int countSubstrings(string s) {
        int res = 0;
        for (int i = 0; i < 2 * s.size() - 1; ++i) {
            int left = i / 2, right = i / 2 + i % 2;
            while (left >= 0 && right < s.size() && s[left] == s[right]) {//中心扩散
                ++res;
                --left;
                ++right;
            }
        }
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

动态规划

其实思路和上面的差不多，感觉有点强行dp的意思，dp[i]表示以s[i]为回文中心（左中心）的回文串个数。

class Solution {
public:
    int countSubstrings(string s) {
        vector<int> dp(s.size(), 0);
        for (int i = 0; i < 2 * s.size() - 1; ++i) {
            int left = i / 2, right = i / 2 + i % 2;//left,right为回文中心位置
            while (left >= 0 && right < s.size() && s[left] == s[right]) {//中心扩散
                ++dp[i/2];
                --left;
                ++right;
            }
        }
        return  accumulate(dp.begin(), dp.end(), 0);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

其实比较常见的dp方式是这样的：

定义状态：

• $dp[i][j]$ 表示字符串s在[i,j]区间的子串是否是一个回文串，1代表是，0代表否

状态转移方程：
考虑字符串 “ababa”:

假设我们当前已知 $dp[i+1][j-1]$，我们怎么计算 $dp[i][j]$ 呢？

• 如果 $s[i]!=s[j]$，那么 $dp[i][j]$ 必然为 0 ，因为区间$[i,j]$不可能为回文串
• 如果 $s[i]==s[j]$，那么容易推导 $dp[i][j]=dp[i+1][j-1]$

还需要考虑特殊情况：

• 当 $i==j$ ，单个字符，$dp[i][j]=1$
• 当 $j-i=1$ ，比如 “aa” 这种情况，i、j分别分别指向前后的 a ，此时这两者中间就不存在$dp[i+1][j-1]$ 了，因为两者已经相邻了。所以此时如果 $s[i]==s[j]$ 那就为1，否则为0。

综上，状态转移方程为：

• 如果 $s[i]!=s[j]$，$dp[i][j]=0$
• 如果 $s[i]==s[j]$， 如果 $j-i<2||dp[i+1][j-1]==1$，那么dp[i][j] = 1，否则为0

考虑状态初始化：全部初始化为 0 即可。

状态转移终点：遍历完字符串

class Solution {
public:
    int countSubstrings(string s) {
        //dp[i][j] 表示字符串s在[i,j]区间的子串是否是一个回文串
        vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
        int res = 0;
        for (int j = 0; j < s.size(); ++j) {
            for(int i = 0; i <= j; ++i){
                if(s[i] == s[j] && (j - i < 2 || dp[i+1][j-1] == 1)){
                    dp[i][j] = 1;//注意i, j的顺序，本题比较特殊
                    ++res;
                }
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

对于字符串 “ababa”，完整的dp数组实在这样的：

1 0 1 0 1 
0 1 0 1 0 
0 0 1 0 1 
0 0 0 1 0 
0 0 0 0 1 
1
2
3
4
5

对于区间 [i, j] ，j是区间右端点，i是区间左端点，j要放在外层循环，i要放在内层循环。当区间右端点 j 右移一位，内层循环区间左端点 i 要在区间 [i, 当前j] 内遍历, 计算回文子串个数。