困难

问题描述

给定一个字符串 s，返回 s 中不同的非空「回文子序列」个数 。

通过从 s 中删除 0 个或多个字符来获得子序列。

如果一个字符序列与它反转后的字符序列一致，那么它是「回文字符序列」。

如果有某个 i , 满足 ai != bi ，则两个序列 a1, a2, ... 和 b1, b2, ... 不同。

注意：

• 结果可能很大，你需要对 109 + 7 取模 。

示例 1：

输入：s = 'bccb'
输出：6
解释：6 个不同的非空回文子字符序列分别为：'b', 'c', 'bb', 'cc', 'bcb', 'bccb'。
注意：'bcb' 虽然出现两次但仅计数一次。

示例 2：

输入：s = 'abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba'
输出：104860361
解释：共有 3104860382 个不同的非空回文子序列，104860361 对 109 + 7 取模后的值。

提示：

• 1 <= s.length <= 1000
• s[i] 仅包含 'a', 'b', 'c' 或 'd'

动态规划

假设 $dp[i][j]$ 为字符串 $s$ 中 $[i,j]$ 范围内回文子序列的个数，那么最终答案为 $dp[0][n-1]$。

然后需要思考状态如何转移。因为字符串只由 $a、b、c、d$ 四种字母组成，组成的回文字符串的边缘字符也只会是这四种，那么枚举这四个字母作为回文边缘字符的方案数并求和，就能统计到全部的回文数。

假设当前枚举到的字符为 k：

• 当 $s_i \dots s_j$ 中并不存在字符 $k$，说明 $s_i \dots s_j$ 中以字符 $k$ 作为边缘字符的回文串的方案并不存在，返回 0
• 当 $s_i \dots s_j$ 中并存在字符 $k$，假设 $k$ 在字符串的最小坐标与最大坐标分别为 $l$ 和 $r$ 会有以下情况:
  • $l = r$，此时 $s_i \dots s_j$ 中以字符 $k$ 作为边缘字符的回文串的方案只有一种，就是 $k$
  • $l = r - 1$，此时 $s_i \dots s_j$ 中以字符 $k$ 作为边缘字符的回文串的方案有两种，分别是 $kk$ 和 $k$
  • $l < r - 1$，此时$s_i \dots s_j$ 中以字符 $k$ 作为边缘字符的回文串的方案有 $kk$ 和 $k$两种，再加上 $dp[l+1][r-1]$ 范围内的全部方案数，即 $ks_{l+1}\dots s_{r-1}k$ 这样合法的方案数。

最终状态转移方程为：

$$\sum_{\alpha=a}^d dp(i, j)= \begin{cases} dp(i, j) & l = -1 \vee r = -1\\ dp(i, j) + 1 & l = r\\ dp(i, j) + 2 & l = r - 1 \\ dp(i, j) + dp(l + 1, r - 1) + 2 & l < r - 1 \end{cases}$$

要找到边缘字符的最小坐标与最大坐标，可以构建两个个长度为 $4$ 的数组 $L$ 和 $R$， 分别记录当前长度的字符串中对应字符的最小坐标与最大坐标。第三种情况需要用到 $dp[l+1][r-1]$，因此 $i$ 从大到小枚举，$j$ 从小到大枚举，这样就能确保 $dp[l+1][r-1]$ 在计算 $dp[i][j]$ 前是算好的。因为 $i$ 是从大到小枚举，$j$ 是从小到大枚举，这样也使得$L$ 和 $R$ 中的数据是正确的。

/**
 * @param {string} s
 * @return {number}
 */
var countPalindromicSubsequences = function (s) {
  const MOD = Math.pow(10, 9) + 7
  const L = new Array(4)
  const R = new Array(4)
  const n = s.length
  const dp = new Array(n).fill(0).map(() => new Array(n).fill(0))
  L.fill(-1)
  for (let i = n - 1; i > -1; i--) {
    L[s[i].charCodeAt(0) - 'a'.charCodeAt(0)] = i
    R.fill(-1)
    for (let j = i; j < n; j++) {
      R[s[j].charCodeAt(0) - 'a'.charCodeAt(0)] = j
      for (let k = 0; k < 4; k++) {
        const l = L[k]
        const r = R[k]
        if (l === -1 || r === -1) continue
        if (l === r) dp[i][j] = (dp[i][j] + 1) % MOD
        else if (l === r - 1) dp[i][j] = (dp[i][j] + 2) % MOD
        else dp[i][j] = (dp[i][j] + dp[l + 1][r - 1] + 2) % MOD
      }
    }
  }
  return dp[0][n - 1]
}

• 时间复杂度：$O(4 \times n^2)$
• 空间复杂度：$O(n^2)$