leetcode刷题笔记-647.回文子串

题目

https://leetcode.cn/problems/palindromic-substrings/

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

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

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

1
2
3
4
5
6
7
8
9
示例 1：
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"

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

提示：

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

思路一：双指针法

我们可以遍历整个字符串，用双指针法从当前下标开始扩张寻找回文子串。找寻相同的字符，如果找到了，则将结果集加一（回文子串个数）。

这里需要注意的是，回文子串有两种情况，一种是奇数长度，我们从中间位置开始扩张就OK了，另外一种是偶数长度，我们必须从中间两位开始扩张。

这个思路比较好理解，所以直接上代码。主要还是注意奇数和偶数这两种不同的回文子串长度。偶数情况可以从(i-1,i)开始找，也可以从(i,i+1)开始找，最终结果都是等价的。

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
class Solution {
public:
    int countSubstrings(string s) {
        if (s.size() <= 1) {
            return s.size();
        }
        int result = 0;
        for (int i = 0; i < s.size(); i++) {
            result += subStringExtend(s, i, i, s.size());     // 奇数
            result += subStringExtend(s, i, i + 1, s.size()); // 偶数
        }
        return result;
    }
    // 从left/right开始往两头扩展，返回最长回文子串长度
    // 分为二者相等（奇数长度）二者不等（偶数长度）的情况
    int subStringExtend(const string& s, int left, int right, int end) {
        int result = 0; // 字符自己也认为是一个长度
        while (left >= 0 && right < end && s[left] == s[right]) {
            left--;
            right++;
            // 结果长度
            result++;
        }
        return result;
    }
};

image.png

思路二：动态规划

动态规划的思路就在516最长回文子序列题目里面接触过了。

动态规划的思路主要还是在于回文子串的特性是只需要判断首末两个字符是否相同。如果相同，再根据之前判断的结果，看这两个字符中间的部分是否回文，就能得出整体是否回文。

定义二维bool数组dp，长和宽都是字符串的长度；dp[i][j]的含义是i和j之间的子串是否为回文子串。

此时递推就只有s[i]==s[j]的情况需要进行操作，分为三种长度

  1. 长度为1，一个字符是回文；
  2. 长度为2，两个字符相同，比如aa，也是回文；
  3. 长度大于2，可能是奇数回文也可能是偶数回文子串，判断dp[i+1][j-1]是否为true。

根据这个递推关系，i和j的遍历顺序也需要进行修改，首先j肯定大于i，所以j是从i开始正序遍历的（因为j依赖于j-1）；而i依赖于i+1，所以i是从最后一个字符开始倒叙遍历的。

初始化的时候，只需要初始化矩阵中i和j相等的部分，相当于一个字符，是回文子串。

完整代码如下

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
class Solution {
public:
    int countSubstrings(string s) {
        if (s.size() <= 1) {
            return s.size();
        }
        // 代表s中i和j下标之间是否是回文子串
        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
        // 初始化，i和j相同的时候肯定是回文，初始化为true
        for (int i = 0; i < s.size(); i++) {
            dp[i][i] = true;
        }
        int result = 0;
        // 开始遍历，依赖项是i+1和j-1，所以i倒叙遍历，j正序遍历
        for (int i = s.size() - 1; i >= 0; i--) {
            for (int j = i; j < s.size(); j++) {
                if (s[i] == s[j]) {
                    // 只有一个字符，或者两个字符，是回文
                    if (abs(i - j) + 1 <= 2) {
                        result++;
                        dp[i][j] = true;
                    }
                    // 偶数回文和奇数回文的情况等价，需要判断中间是否回文
                    else if (dp[i + 1][j - 1]) {
                        result++;
                        dp[i][j] = true;
                    }
                }
            }
        }
        return result;
    }
};

image.png