0115. Distinct Subsequences =========================== 题目信息 -------- :题号: 0115. 不同的子序列 :难度: Hard :主题: 字符串、组合计数、动态规划、滚动数组 :原题: `LeetCode 0115 `_ :重点: 将选或不选的指数搜索合并为源前缀与目标前缀状态,再用逆序更新保证一个源下标只使用一次 题目重述 -------- 给定字符串 ``s`` 和 ``t``,统计有多少种方式可以从 ``s`` 删除零个或多个字符,使剩余字符保持原相对顺序 并恰好组成 ``t``。 不同方案按保留的 ``s`` 下标序列区分:即使字符值相同,只要选择了不同源下标,就要分别计数。删除不能改变 字符顺序,也不能重复使用同一下标。最终答案保证能放入 32 位有符号整数。 ``s``、``t`` 长度都在 ``1..1000`` 范围内,只包含小写英文字母。 自建示例 -------- * 重复字符产生多种下标方案:``s = "banana"``、``t = "ban"``,返回 ``3``,可选择下标 ``(0,1,2)``、``(0,1,4)``、``(0,3,4)``; * 相对顺序不符:``s = "abc"``、``t = "ca"``,返回 ``0``; * 目标更长:``s = "ab"``、``t = "aba"``,返回 ``0``; * 全部字符相同:``s = "aaaa"``、``t = "aa"``,返回 ``6``,对应从四个下标中选择两个。 C++ 实现 -------- .. code-block:: cpp #include #include #include #include class Solution { private: static constexpr long long LIMIT = INT_MAX; long long cappedAdd(long long first, long long second) { return std::min(LIMIT, first + second); } int tableDynamicProgramming(const std::string& s, const std::string& t) { const int sourceLength = static_cast(s.size()); const int targetLength = static_cast(t.size()); std::vector> ways( sourceLength + 1, std::vector(targetLength + 1)); for (int sourceCount = 0; sourceCount <= sourceLength; ++sourceCount) { ways[sourceCount][0] = 1; } for (int sourceCount = 1; sourceCount <= sourceLength; ++sourceCount) { for (int targetCount = 1; targetCount <= targetLength; ++targetCount) { ways[sourceCount][targetCount] = ways[sourceCount - 1][targetCount]; if (s[sourceCount - 1] == t[targetCount - 1]) { ways[sourceCount][targetCount] = cappedAdd(ways[sourceCount][targetCount], ways[sourceCount - 1][targetCount - 1]); } } } return static_cast(ways[sourceLength][targetLength]); } int rollingDynamicProgramming(const std::string& s, const std::string& t) { if (t.size() > s.size()) { return 0; } std::vector ways(t.size() + 1); ways[0] = 1; for (char sourceCharacter : s) { for (int targetCount = static_cast(t.size()); targetCount >= 1; --targetCount) { if (sourceCharacter == t[targetCount - 1]) { ways[targetCount] = cappedAdd(ways[targetCount], ways[targetCount - 1]); } } } return static_cast(ways[t.size()]); } public: int numDistinct(std::string s, std::string t) { return rollingDynamicProgramming(s, t); } }; 题解 ---- 选与不选的搜索树 ~~~~~~~~~~~~~~~~ 扫描 ``s`` 时,每个位置都有两种决定:删除当前字符,或在它与当前所需目标字符相等时保留它。枚举所有决定 形成最多 ``2^n`` 条分支;到达源字符串末尾时,恰好匹配完 ``t`` 的分支计为一种方案。 这种枚举是正确的,因为每个保留下标序列对应唯一一组“选或不选”决定。相同字符位于不同下标时属于不同 分支,正好符合题目的计数口径。 指数搜索重复了大量后续问题。不同选择可能到达同一状态:已经处理 ``s`` 的前 ``i`` 个字符,也已经组成 ``t`` 的前 ``j`` 个字符;从这里继续的方案数只取决于 ``i``、``j``,与更早具体选择了哪些下标无关。 二维前缀状态 ~~~~~~~~~~~~ 定义 ``ways[i][j]`` 为使用 ``s`` 前 ``i`` 个字符组成 ``t`` 前 ``j`` 个字符的下标方案数。 空目标 ``j = 0`` 始终有一种方案:删除当前源前缀的全部字符,所以 ``ways[i][0] = 1``。空源无法组成非空 目标,初始化的 ``ways[0][j] = 0`` 保持不变。 观察新加入源前缀的最后下标 ``i - 1``,全部方案可以按是否使用它分成两类: * 不使用 ``s[i - 1]``:方案完全来自 ``ways[i - 1][j]``; * 若 ``s[i - 1] == t[j - 1]``,使用它作为目标前缀最后字符:此前必须组成 ``t`` 前 ``j - 1`` 个字符, 方案来自 ``ways[i - 1][j - 1]``。 .. code-block:: text ways[i][j] = ways[i - 1][j] if s[i - 1] == t[j - 1]: ways[i][j] += ways[i - 1][j - 1] 两类方案按是否包含源下标 ``i - 1`` 划分,互斥且覆盖全部可能,因此可以直接相加。二维表把所有到达同一 前缀状态的指数分支合并,每个状态只计算一次。 一维状态压缩 ~~~~~~~~~~~~ 第 ``i`` 行只读取第 ``i - 1`` 行,可以把源前缀维度压缩掉。处理当前 ``sourceCharacter`` 前, ``ways[j]`` 表示旧源前缀组成目标前 ``j`` 个字符的方案数;处理后,它要加上旧的 ``ways[j - 1]``。 目标下标必须从右向左更新。若从左向右,``ways[j - 1]`` 已经包含当前源字符,随后更新 ``ways[j]`` 时会在 同一方案中再次使用这个下标。例如只处理一个字符 ``'a'``、目标为 ``"aa"``,正序会先令 ``ways[1] = 1``, 再错误地用这个新值令 ``ways[2] = 1``。逆序保证读取的左邻居仍属于上一轮源前缀。 状态走读 ~~~~~~~~ 对 ``s = "banana"``、``t = "ban"``,``ways`` 各位置依次表示目标前缀 ``""``、``"b"``、``"ba"``、 ``"ban"``: .. list-table:: :header-rows: 1 * - 已处理源前缀 - ``ways`` - 新增含义 * - ``""`` - ``[1,0,0,0]`` - 只有空目标 * - ``"b"`` - ``[1,1,0,0]`` - 下标 0 可形成 ``"b"`` * - ``"ba"`` - ``[1,1,1,0]`` - 得到第一种 ``"ba"`` * - ``"ban"`` - ``[1,1,1,1]`` - 得到第一种 ``"ban"`` * - ``"bana"`` - ``[1,1,2,1]`` - 两个 ``a`` 下标可形成 ``"ba"`` * - ``"banan"`` - ``[1,1,2,3]`` - 两种旧 ``"ba"`` 加入当前 ``n`` * - ``"banana"`` - ``[1,1,3,3]`` - 最终完整目标仍为 3 种 数值上界处理 ~~~~~~~~~~~~ 题目只保证最终完整目标计数适合 32 位;某些较短目标前缀可能拥有更多选择。代码把每个状态饱和到 ``INT_MAX``,并使用 ``long long`` 完成两个已饱和值的加法。 转移只有非负加法。如果某个超过上界的前缀状态能够继续扩展成完整目标,固定任意一种后缀扩展后,它的每个 不同前缀方案都会产生不同完整下标序列,最终答案也会超过上界,与题目保证矛盾。因此被饱和的状态不会改变 合法最终答案;不能贡献到最终目标的巨大状态本来也与返回值无关。 主解与复杂度 ~~~~~~~~~~~~ 目标比源更长时无法选择足够下标,主解直接返回 ``0``。公开入口采用逆序一维 DP,因为它保留二维转移的旧行 语义,把工作空间从 ``O(nm)`` 压缩为 ``O(m)``。 设 ``n = s.length``、``m = t.length``。二维与一维方案都计算至多 ``nm`` 个字符配对状态,时间 ``O(nm)``;二维空间 ``O(nm)``,一维工作空间 ``O(m)``。返回值只占常数空间。