LeetCode 730. 统计不同回文子序列

2022-04-06 HGNULB 约 7 分钟

文章信息 6 个分类 2 个标签

分类

LeetCode CodeTop 困难未解决 1-2 美团

题目描述

✅ 730. 统计不同回文子序列

题意分析

统计字符串中不同的非空回文子序列数量，对 10^9+7 取模。子序列不要求连续，但必须保持原顺序；不同下标组合得到相同字符串时只计一次。

解法：区间动态规划 + 同字符位置

核心思路

[!blue]

定义 dp[i][j] 为闭区间 [i, j] 中不同非空回文子序列的数量。单字符只有一种，故 dp[i][i] = 1；空区间贡献 0。按区间长度从小到大计算，就能由已经求好的内部区间得到当前答案。

若 s[i] != s[j]，回文不能同时使用这两个字符作为首尾，所以它一定属于 [i+1, j] 或 [i, j-1]。两者共同包含的回文正是中间 [i+1, j-1] 的回文，合并后减去一次重复，得到 dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]。

若两端都为字符 c，设中间区间的答案为 S。候选来自四部分：中间原有的 S 种回文、给每种中间回文外包两个 c 得到的 S 种新形式，以及单独的 c 和 cc。外包不同回文会得到不同字符串，但可能与中间已经存在的字符串重复，需要按内部 c 的数量分类。

内部没有 c：四部分互不重复，答案为 2*S+2。

内部只有一个 c：单独的 c 已被 S 计入，但内部无法组成 cc 或更长的首尾为 c 的回文，所以只额外增加 cc，答案为 2*S+1。

内部至少有两个 c：c 和 cc 都已计入 S。设内部最左、最右的 c 位于 l、r，重复的是那些内部已经能组成的 c + 回文 + c。这些中间回文恰好可以从 [l+1, r-1] 取得，因此要减去 dp[l+1][r-1]，答案为 2*S-dp[l+1][r-1]。

最后一种情况必须取内部最左、最右的 c：任何内部首尾为 c 的回文，都可以改用这两个最外侧位置作为首尾而保持内容不变；反过来，它们中间的每个非空回文也都能外包成一个重复项。因此减去的集合既完整，也不会多减。

字符只有 a 到 d，预处理 nextPos[p][c] 表示从 p 开始向右第一个 c 的位置，prevPos[p][c] 表示从 p 向左第一个 c 的位置。查询 nextPos[i+1][c] 和 prevPos[j-1][c] 得到 l、r，不存在或 l > r 表示内部没有 c，l == r 表示只有一个。每次转移取模后若为负，再加一次模数修正。

解题步骤

预处理相同字符的下一位置和上一位置。

将单字符区间初始化为一。

按区间长度递增，分别处理两端不同和相同的情况。

减法后修正到非负模数范围，返回完整区间。

代码实现

class Solution {
    public int countPalindromicSubsequences(String s) {
        int n = s.length();
        int mod = 1_000_000_007;
        char[] a = s.toCharArray();

        // 位置表包含当前下标，转移查询从 i+1 到 j-1 的内部同字符。
        int[][] nextPos = new int[n][4];
        int[][] prevPos = new int[n][4];

        int[] last = new int[4];

        Arrays.fill(last, -1);

        for (int i = 0; i < n; i++) {
            int c = a[i] - 'a';

            last[c] = i;

            for (int t = 0; t < 4; t++) {
                prevPos[i][t] = last[t];
            }
        }

        Arrays.fill(last, -1);

        for (int i = n - 1; i >= 0; i--) {
            int c = a[i] - 'a';

            last[c] = i;

            for (int t = 0; t < 4; t++) {
                nextPos[i][t] = last[t];
            }
        }

        long[][] dp = new long[n][n];

        for (int i = 0; i < n; i++) {
            // 单字符只有一种回文；下三角未写位置保持零，表示空区间。
            dp[i][i] = 1;
        }

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;

                if (a[i] != a[j]) {
                    dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1];
                } else {
                    int ch = a[i] - 'a';
                    // 定位两端之间最左和最右的同字符，区分重复数量。
                    int l = nextPos[i + 1][ch];
                    int r = prevPos[j - 1][ch];

                    if (l == -1 || l > r) {
                        dp[i][j] = dp[i + 1][j - 1] * 2 + 2;
                    } else if (l == r) {
                        dp[i][j] = dp[i + 1][j - 1] * 2 + 1;
                    } else {
                        // 内部至少两个同字符时，减去会被重复外包的中间回文。
                        dp[i][j] = dp[i + 1][j - 1] * 2 - dp[l + 1][r - 1];
                    }
                }

                dp[i][j] %= mod;

                // 包含减法的模运算需要将负余数修正到非负范围。
                if (dp[i][j] < 0) {
                    dp[i][j] += mod;
                }
            }
        }

        return (int) dp[0][n - 1];
    }
}

func countPalindromicSubsequences(s string) int {
    const mod int64 = 1_000_000_007
    n := len(s)
    a := []byte(s)

    // 位置表包含当前下标，转移查询从 i+1 到 j-1 的内部同字符。
    nextPos := make([][4]int, n)
    prevPos := make([][4]int, n)

    last := [4]int{
        -1,
        -1,
        -1,
        -1,
    }
    for i := 0; i < n; i++ {
        last[a[i]-'a'] = i
        for t := 0; t < 4; t++ {
            prevPos[i][t] = last[t]
        }
    }

    last = [4]int{
        -1,
        -1,
        -1,
        -1,
    }
    for i := n - 1; i >= 0; i-- {
        last[a[i]-'a'] = i
        for t := 0; t < 4; t++ {
            nextPos[i][t] = last[t]
        }
    }

    dp := make([][]int64, n)
    for i := range dp {
        dp[i] = make([]int64, n)
        // 单字符只有一种回文；下三角未写位置保持零，表示空区间。
        dp[i][i] = 1
    }

    for length := 2; length <= n; length++ {
        for i := 0; i+length-1 < n; i++ {
            j := i + length - 1
            if a[i] != a[j] {
                dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]
            } else {
                ch := a[i] - 'a'
                // 定位两端之间最左和最右的同字符，区分重复数量。
                l := nextPos[i+1][ch]
                r := prevPos[j-1][ch]
                if l == -1 || l > r {
                    dp[i][j] = dp[i+1][j-1]*2 + 2
                } else if l == r {
                    dp[i][j] = dp[i+1][j-1]*2 + 1
                } else {
                    // 内部至少两个同字符时，减去会被重复外包的中间回文。
                    dp[i][j] = dp[i+1][j-1]*2 - dp[l+1][r-1]
                }
            }

            dp[i][j] %= mod
            // 包含减法的模运算需要将负余数修正到非负范围。
            if dp[i][j] < 0 {
                dp[i][j] += mod
            }
        }
    }

    return int(dp[0][n-1])
}

复杂度分析

时间复杂度：$O(n^2)$，n 为字符串长度，同字符位置预处理为 $O(n)$，每个区间进行常数时间转移。

空间复杂度：$O(n^2)$，区间状态表；同字符位置表另占 $O(n)$。

关键点总结

[!green]

去重对象是结果字符串，不是下标组合。

内部边界使用最左和最右的同字符位置。

所有状态保存的是取模后的数量，转移减法需要统一处理负值。

易错点总结

[!yellow]

直接套用普通回文子序列计数：同一个字符串会重复计算。

两端相同总是加二：内部已有同字符时产生重复。

选取内部最靠近彼此的一对字符：减去的区间不符合去重关系。

长度从大到小计算：依赖的小区间尚未得到结果。

相似题目

题目	难度	关联与区别
516. 最长回文子序列	中等	同样使用回文区间结构，原题只求最长长度，本题计所有不同内容，必须处理重复贡献。
1930. 长度为 3 的不同回文子序列	中等	原题只数长度3的不同回文，本题允许任意长度，需要更完整的区间去重递推。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2022/93389645

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！