力扣题解-647. 回文子串(动态规划)_力扣647

题目：647. 回文子串

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：“abc”
输出：3
解释：三个回文子串: “a”, “b”, “c”
示例 2：
输入：“aaa”
输出：6
解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”
提示：
输入的字符串长度不会超过 1000 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindromic-substrings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解1：动态规划

回文串是一个经典的动态规划问题。动态规划问题的解题关键在于通过对原问题及其子问题的分析，然后定义问题的动态规划状态。这一步是动态规划的核心，当然也是动态规划类问题的难点所在。在确定状态的定义后，剩下的就是找出状态转移方程。
有时候，针对同样的问题，由于分析问题的出发点不同导致我们对相同的问题定义了不同的状态，将会得到不同的状态转移方程。问题解的复杂度也截然不同。
这里给出针对回文串的基本动态规划思路。
举个例子，串"a"是一个回文串。那么，串`“bab”，也是一个回文串。根据这个特点，我们可以定义该回文串问题的动态规划状态。

定义状态

令dp[i][j]表示子串以i位置开始，以j位置结尾的子串s[i,...,j]是否为回文串，则dp[i][j]可以通过子串s[i+1,...,j-1]的结果dp[i+1][j-1]进行状态转移得到。

状态转移方程

那么，我们定义状态转移方程：

$dp[i][j]=dp[i+1][j-1]\&\&(s[i]==s[j])$

其中，$n=s.length$，$0\le i,j\le n-1$，且 $i+1\le j-1$。

初始值/边界条件

首先，单个字符的子串是回文串，有$dp[i][i]=true，0\le i\le n-1$；
其次，不满足状态转移条件的边界情况，$i+1>j-1$，即 $j-i==1$； 有$dp[i][i+1]=(s[i]==s[i+1])$。
结合状态转移方程和边界条件，可细化状态转移方程为：

    if (s[i] == s[j]) {
        if (i == j) dp[i][j] = true;
        else if (i == j - 1) dp[i][j] = true;
        else dp[i][j] = dp[i+1][j-1];
    }
    else dp[i][j] = false;
1
2
3
4
5
6

最优解

$sum(dp[i][j])，当dp[i][j]==true时。$

复杂度分析

时间复杂度：定义了两个变量$i，j$，分别循环$n$次，因此时间复杂度为$\Theta (n^2)$。
空间复杂度：额外定义了二维数组dp，因此空间复杂度为$\Theta (n^2)$。

代码

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.length();
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        int ans = 0;
        //由于状态转移的方向是由短子串向长子串进行，因此我们在遍历子串时需要遵循这个原则。
        for (int l = 0; l < n; l++) {//变量l即为控制子串的长度
            for (int i = 0; i < n; i++) {
                int j = i + l;
                if (j >= n) {
                    continue;
                }
                if (i == j) {
                    dp[i][j] = true;
                } else if (i + 1 <= j - 1) {
                    dp[i][j] = dp[i+1][j-1] && (s[i] == s[j]);
                } else {
                    dp[i][j] = s[i] == s[j];
                }
                if (dp[i][j]) {
                    ans++;
                }
            }
        }
        return ans;
    }
};
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