Hard

题目描述

给定一个字符串 s，返回 s 中不同的非空回文子序列个数。由于答案可能很大，返回答案对 109 + 7 取模的结果。

字符串的子序列是通过删除字符串中零个或多个字符而得到的。

如果一个序列与它的反转相等，那么它是回文的。

如果存在某个 i 使得 ai != bi，那么两个序列 a1, a2, ... 和 b1, b2, ... 不同。

示例 1：

输入：s = "bccb"
输出：6
解释：6 个不同的非空回文子序列分别为：'b', 'c', 'bb', 'cc', 'bcb', 'bccb'。
注意：'bcb' 只能被计算一次，即使它出现了两次。

示例 2：

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

提示：

  • 1 <= s.length <= 1000
  • s[i] 是 'a'、'b'、'c' 或 'd' 中的一个

解题思路

这是一道经典的动态规划题目，核心思想是利用区间 DP 来计算每个子串中不同回文子序列的数量。

基本思路： 设 dp[i][j] 表示字符串 s[i...j] 中不同回文子序列的数量。

状态转移： 对于每个字符 c（‘a’、‘b’、‘c’、’d’），我们需要考虑以 c 开头和结尾的回文子序列：

  1. 如果区间 [i,j] 内没有字符 c，那么以 c 开头结尾的回文子序列数量为 0
  2. 如果区间 [i,j] 内只有一个字符 c，那么只有一个回文子序列：单个字符 c
  3. 如果区间 [i,j] 内有多个字符 c，设最左边的 c 在位置 left，最右边的 c 在位置 right，那么以 c 开头结尾的回文子序列数量等于 dp[left+1][right-1] + 2（加2是因为单个 c 和两个 c 组成的 cc）

优化细节：

  • 预处理每个位置左右最近的相同字符位置，避免重复计算
  • 使用模运算防止溢出
  • 区间长度从小到大进行动态规划

时间复杂度为 O(n²)，空间复杂度为 O(n²)，其中 n 是字符串长度。

代码实现

class Solution {
public:
    int countPalindromicSubsequences(string s) {
        int n = s.length();
        const int MOD = 1000000007;
        
        // dp[i][j] 表示 s[i...j] 中不同回文子序列的数量
        vector<vector<int>> dp(n, vector<int>(n, 0));
        
        // 预处理：找到每个位置左边和右边最近的相同字符位置
        vector<vector<int>> next(n, vector<int>(4, n));
        vector<vector<int>> prev(n, vector<int>(4, -1));
        
        // 从右到左扫描，计算 next 数组
        for (int i = n - 1; i >= 0; i--) {
            if (i < n - 1) {
                for (int j = 0; j < 4; j++) {
                    next[i][j] = next[i + 1][j];
                }
            }
            next[i][s[i] - 'a'] = i;
        }
        
        // 从左到右扫描，计算 prev 数组
        for (int i = 0; i < n; i++) {
            if (i > 0) {
                for (int j = 0; j < 4; j++) {
                    prev[i][j] = prev[i - 1][j];
                }
            }
            prev[i][s[i] - 'a'] = i;
        }
        
        // 动态规划
        for (int len = 1; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                
                for (int c = 0; c < 4; c++) {
                    int left = next[i][c];
                    int right = (j >= 0) ? prev[j][c] : -1;
                    
                    if (left <= j && right >= i) {
                        if (left == right) {
                            dp[i][j] = (dp[i][j] + 1) % MOD;
                        } else {
                            dp[i][j] = (dp[i][j] + dp[left + 1][right - 1] + 2) % MOD;
                        }
                    }
                }
            }
        }
        
        return dp[0][n - 1];
    }
};

class Solution:
    def countPalindromicSubsequences(self, s: str) -> int:
        n = len(s)
        MOD = 10**9 + 7
        
        # dp[i][j] 表示 s[i:j+1] 中不同回文子序列的数量
        dp = [[0] * n for _ in range(n)]
        
        # 预处理：找到每个位置左边和右边最近的相同字符位置
        next_pos = [[n] * 4 for _ in range(n)]
        prev_pos = [[-1] * 4 for _ in range(n)]
        
        # 从右到左扫描，计算 next_pos 数组
        for i in range(n - 1, -1, -1):
            if i < n - 1:
                for j in range(4):
                    next_pos[i][j] = next_pos[i + 1][j]
            next_pos[i][ord(s[i]) - ord('a')] = i
        
        # 从左到右扫描，计算 prev_pos 数组
        for i in range(n):
            if i > 0:
                for j in range(4):
                    prev_pos[i][j] = prev_pos[i - 1][j]
            prev_pos[i][ord(s[i]) - ord('a')] = i
        
        # 动态规划
        for length in range(1, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                
                for c in range(4):
                    left = next_pos[i][c]
                    right = prev_pos[j][c] if j >= 0 else -1
                    
                    if left <= j and right >= i:
                        if left == right:
                            dp[i][j] = (dp[i][j] + 1) % MOD
                        else:
                            dp[i][j] = (dp[i][j] + dp[left + 1][right - 1] + 2) % MOD
        
        return dp[0][n - 1]

public class Solution {
    public int CountPalindromicSubsequences(string s) {
        int n = s.Length;
        const int MOD = 1000000007;
        
        // dp[i][j] 表示 s[i...j] 中不同回文子序列的数量
        int[,] dp = new int[n, n];
        
        // 预处理：找到每个位置左边和右边最近的相同字符位置
        int[,] next = new int[n, 4];
        int[,] prev = new int[n, 4];
        
        // 初始化 next 数组
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 4; j++) {
                next[i, j] = n;
                prev[i, j] = -1;
            }
        }
        
        // 从右到左扫描，计算 next 数组
        for (int i = n - 1; i >= 0; i--) {
            if (i < n - 1) {
                for (int j = 0; j < 4; j++) {
                    next[i, j] = next[i + 1, j];
                }
            }
            next[i, s[i] - 'a'] = i;
        }
        
        // 从左到右扫描，计算 prev 数组
        for (int i = 0; i < n; i++) {
            if (i > 0) {
                for (int j = 0; j < 4; j++) {
                    prev[i, j] = prev[i - 1, j];
                }
            }
            prev[i, s[i] - 'a'] = i;
        }
        
        // 动态规划
        for (int len = 1; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                
                for (int c = 0; c < 4; c++) {
                    int left = next[i, c];
                    int right = (j >= 0) ? prev[j, c] : -1;
                    
                    if (left <= j && right >= i) {
                        if (left == right) {
                            dp[i, j] = (dp[i, j] + 1) % MOD;
                        } else {
                            dp[i, j] = (dp[i, j] + dp[left + 1, right - 1] + 2) % MOD;
                        }
                    }
                }
            }
        }
        
        return dp[0, n - 1];
    }
}

var countPalindromicSubsequences = function(s) {
    const MOD = 1000000007;
    const n = s.length;
    const memo = {};
    
    function dp(i, j, c) {
        if (i > j) return 0;
        
        const key = `${i}-${j}-${c}`;
        if (key in memo) return memo[key];
        
        let result = 0;
        
        if (c === '') {
            for (let ch of 'abcd') {
                result = (result + dp(i, j, ch)) % MOD;
            }
        } else {
            let left = -1, right = -1;
            
            for (let k = i; k <= j; k++) {
                if (s[k] === c) {
                    if (left === -1) left = k;
                    right = k;
                }
            }
            
            if (left === -1) {
                result = 0;
            } else if (left === right) {
                result = 1;
            } else {
                result = 2;
                for (let ch of 'abcd') {
                    result = (result + dp(left + 1, right - 1, ch)) % MOD;
                }
            }
        }
        
        return memo[key] = result;
    }
    
    return dp(0, n - 1, '');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n²)需要填充 n×n 的 dp 数组，每个位置需要遍历 4 个字符
空间复杂度O(n²)dp 数组、next 数组和 prev 数组的空间开销

相关题目