跳转至

647. 回文子串

力扣链接(中等)：https://leetcode.cn/problems/palindromic-substrings

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

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

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

示例 1：

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

示例 2：

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

提示：

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

个人题解

动态规划

本题和大部分动态规划题目不同，状态转移并不是简单的“后依赖前”的关系，也就是说 dp[i] 似乎和 dp[i - 1] 等没有直接联系。回归到“回文串”的定义：某一个串 从前向后 和 从后向前 遍历值是相同的，这样的串就具备回文性质。如何用动态规划的思想去判断一个区间为 [i, j] 串是否是回文串，不难得到这样一些情况：

  1. 当前遍历的子串头尾是相等的，其子情况见下文；
  2. 当前遍历的子串头尾不相等，那自然不是回文串，不用继续判断。

头尾相等时又有几类情况：

  1. 当前子串长度为 1，那么天然是回文串；
  2. 当前子串长度为 2，同样是回文串；
  3. 当前子串长度大于 2，其是否为回文串应该转移为区间 [i + 1, j - 1] 串的状态，即头尾元素如果相等，若中间的子串满足回文性，那么当前串一定也是回文串。

所以定义 bool dp[i][j]：区间 [i, j] 的子串是否为回文串，同时得到一个递推关系：dp[i][j] = dp[i + 1][j - 1]。

关于 dp 的遍历顺序，同样与常规的动态规划题目不同，根据上述递推关系，可知 dp[i][j] 是依赖于 dp[i + 1][j - 1] 的，根据 dp 矩阵示意图来分析遍历顺序：

Text Only
1
2
3
4
5
6
7
8
9
0 ---------------------> [j]
^
|
|
|              dp[i][j]
|      dp[i + 1][j - 1]
|
|
[i]

显然，应该从左下角遍历到右上角，又根据 dp 矩阵的定义知 i <= j，所以 dp 数组填充区域应该为上三角区域。

最终得到遍历顺序：i 从末尾 s.size() - 1 开始遍历，j 从 i 开始遍历。

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int countSubstrings(string s) {
        // dp[i][j] 初始化为 false，表示区间为 [i, j] 的子串不具备回文性质
        vector<vector<bool>> dp(s.size() + 10, vector<bool>(s.size() + 10, false));
        int result = 0;
        for(int i = s.size() - 1; i >= 0; i--) {
            for(int j = i; j < s.size(); j++) {
                if(s[i] == s[j]) {
                    if(i == j || j - i == 1) {
                        dp[i][j] = true;
                        result++;
                    }
                    else if(dp[i + 1][j - 1]) {
                        dp[i][j] = true;
                        result++;
                    }
                }
            }
        }

        return result;
    }
};

双指针

双指针可以优化动态规划 \(O(N^2)\) 的空间复杂度到 \(O(1)\)。

需要注意的是，不要漏掉了中心子串长度为 2 的情况，即以两个元素为中心，向左右遍历的情况。

例如串 aaa，一共有 ["a", "a", "a", "aa", "aa", "aaa"] 种回文子串，如果每次都以单个元素为中心向两边遍历 extend(s, i, i, s.size()) 很明显会漏掉 aa 这种情况，所以要加上 extend(s, i, i + 1, s.size())。

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int countSubstrings(string s) {
        int result = 0;
        for(int i = 0; i < s.size(); i++) {
            result += extend(s, i, i, s.size());
            result += extend(s, i, i + 1, s.size());
        }

        return result;
    }
    int extend(const string &s, int i, int j, int size) {
        int cnt = 0;
        while(i >= 0 && j < size && s[i] == s[j]) {
            cnt++;
            i--;
            j++;
        }

        return cnt;
    }
};