这是 2020 年 8 月 19 日的每日一题。这道题我是用 动态规划 解出来的。但是这题的 动态规划 效果反而不如暴力优化。可以说这道题让我明白了 动态规划 不能滥用。特此记录一下。

题目

给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。

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

示例 1

输入:"abc"
输出:3
解释:三个回文子串: "a", "b", "c"

示例 2

输入:"aaa"
输出:6
解释:6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

动态规划

前排提醒,这道题的 动态规划 是反面教材

首先我们构造一个 dp(i, j) 值为 字符串中 第 i 个字符到 第 j 个字符的子串是否是回文串。

然后思考状态转移,回文子串的两端点字符必须相同,同时拿掉两端点的字符剩下的字符也是回文子串,所以我们可以给出状态转移方程:

dp(i, j) = (  s(i) == s(j) && dp(i+1, j-1)  )

然后是边界条件,当子串长度为 1 或者 2 的时候,也很好处理,这里就不说了。

然后是转移方向,这里方向并不是简单的 i j 二重循环,我们需要定义一个变量 l = j-i+1, 也就是子串的长度,按照 l 从小到大遍历。

然后就 Ok,我们只需在遍历的时候计数就行。直接给出代码:

  • 语言:C++
class Solution {
public:
    int countSubstrings(string s) {
        vector<vector<bool>> dp (
                s.size(), vector<bool>(
                        s.size() , true
                        )
                );
        int result = 0;
        for(int l = 2 ; l <= s.size() ; l ++){
            for(int i = 0 ; i < s.size() - l ; i ++){
                if(l == 1){
                    result ++;
                    continue;
                }
                int j = i +l -1;
                dp[i][j] = dp[i+1][j-1] && s[i] == s[j];
                if (dp[i][j]){
                    result ++;
                }

            }
        }
        return result;

    }
};

这个方法的时间复杂度是 o(n^2),控件复杂度也是 o(n^2)
在这里我直接给结论,这个方法不好。接下来来看官方题解的第一个解法也就是中心拓展法。。

暴力优化 - 中心拓展

首先先来思考暴力法,暴力法就是遍历 所有 子串,这一步需要 o(n^2) 的时间复杂度,然后是判断所有子串是否为回文串,这里需要 o(n) 的时间复杂度(当判断最长的串时候)。所以暴力法时间复杂度为 o(n^3),好像比 动态规划 慢,但是这里暴力法的空间复杂度为 o(1)。所以这道题 动态规划 只是相当于暴力解法以空间换时间。并没有实质上的提升。

这里我们对暴力解法进行优化。首先判断是否是回文串我们依然可以用以上的方法。也就是两端字符相等且内部字符是回文串。

所以我们可以遍历一个 回文串中心,然后不断向两端拓展,并且只有两端点一致的时候才拓展。并在拓展的过程中计数。

这里就涉及到一个奇偶数的问题。因为回文串的中心可以是一个字符,也可以是两个字符。这里我们可以引入一个中间数 k,并且 令 i = ⌊k/2⌋j = i + i mol 2,然后让 k02n-2 遍历,我们就得到了所有可能的包括奇偶数的回文中心。

然后直接上代码吧:

  • 语言:C++
class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size(), ans = 0;
        for (int k = 0; k < 2 * n - 1; k ++) {
            int i = k / 2;
            int j = j + k % 2;
            while (i >= 0 && j < n && s[i] == s[j]) {
                i--;
                j++;
                ans++;
            }
        }
        return ans;
    }
};

这个方法的时间复杂度为 o(n^2),但是空间复杂度为 o(1) ,也就是说这个方法和 动态规划 时间上效率一致,但是省下了 o(n^2) 的空间。

动态规划哪不好

为什么,两种方法的核心都是两端点字符和中间子串的判断。为啥 动态规划 要比 中心拓展 多了一点空间。

其实答案也很简单,因为在 动态规划 的过程中,我们每个函数值最多只用到一次,就是在计算 dp[i-1][j+1] 的时候,我们才需要用到 dp[i][j],而其他时候这个数值是不会用到的。所以我们可以用一个临时变量来表示这个函数。但是为了保证 dp[i][j] 计算完后下一个是 dp[i-1][j+1],中心拓展也就呼之欲出了。

从本质上讲,动态规划 始终是一种用空间换时间的算法。其真正的优势在 dp 函数值会被多次调用的时候才会体现出来。如果每个函数值只会被用到一次,那么 动态规划 带来的只有空间上的浪费。

这道题也就是带来一种警示,你可以使用 动态规划 来思考解题步骤,但当你发现 动态规划 的函数值没有被多次调用的时候,可以尝试思考使用临时变量。大多数状态转变为临时变量的方法就是暴力解法的优化。此时就可以在同样的时间复杂度下省下空间。

后记

其实这道题还有一个在 o(n) 复杂度下的算法,也就是大名鼎鼎的 马拉车 (Manacher) 算法。只不过该算法难度已经超过面试级难度,大概是竞赛级难度。所以有时间在整理吧。这道题主要是告诉我们 动态规划 的一个使用误区。