0091. Decode Ways
=================
题目信息
--------
:题号: 0091. 解码方法
:难度: Medium
:主题: 字符串、动态规划、记忆化搜索、滚动状态
:原题: `LeetCode 0091 `_
:重点: 从枚举一位与两位切分,推导到只保留前两个前缀状态
题目重述
--------
数字 ``1`` 到 ``26`` 分别映射到字母 ``A`` 到 ``Z``。给定一个只包含数字的非空字符串 ``s``,
返回把整个字符串切分为合法编码的方案数。
一位编码只能是 ``1..9``,两位编码只能是 ``10..26``。字符 ``0`` 不能单独解码,也不能作为两位编码的首位。
题目保证最终答案位于 32 位有符号整数范围内。
自建示例
--------
.. code-block:: text
输入:s = "1212"
输出:5
合法切分为 ``1|2|1|2``、``12|1|2``、``1|21|2``、``1|2|12`` 和 ``12|12``。
.. code-block:: text
输入:s = "101"
输出:1
只有 ``10|1`` 合法;``1|01`` 中的 ``0`` 不能单独解码。
.. code-block:: text
输入:s = "230"
输出:0
``0`` 不能单独解码,而 ``30`` 超出 ``10..26``。
C++ 实现
--------
.. code-block:: cpp
#include
#include
class Solution {
private:
bool validPair(char first, char second) {
int value = (first - '0') * 10 + (second - '0');
return 10 <= value && value <= 26;
}
int plainRecursion(const std::string& s, int index) {
if (index == static_cast(s.size())) {
return 1;
}
if (s[index] == '0') {
return 0;
}
int ways = plainRecursion(s, index + 1);
if (index + 1 < static_cast(s.size()) &&
validPair(s[index], s[index + 1])) {
ways += plainRecursion(s, index + 2);
}
return ways;
}
int memoDfs(const std::string& s, int index,
std::vector& memo) {
if (index == static_cast(s.size())) {
return 1;
}
if (s[index] == '0') {
return 0;
}
if (memo[index] != -1) {
return memo[index];
}
int ways = memoDfs(s, index + 1, memo);
if (index + 1 < static_cast(s.size()) &&
validPair(s[index], s[index + 1])) {
ways += memoDfs(s, index + 2, memo);
}
memo[index] = ways;
return ways;
}
int memoizedSearch(const std::string& s) {
std::vector memo(s.size(), -1);
return memoDfs(s, 0, memo);
}
int tableDp(const std::string& s) {
int n = static_cast(s.size());
std::vector dp(n + 1);
dp[0] = 1;
for (int length = 1; length <= n; ++length) {
if (s[length - 1] != '0') {
dp[length] += dp[length - 1];
}
if (length >= 2 &&
validPair(s[length - 2], s[length - 1])) {
dp[length] += dp[length - 2];
}
}
return dp[n];
}
int rollingDp(const std::string& s) {
int twoBack = 1;
int oneBack = s[0] == '0' ? 0 : 1;
for (int length = 2;
length <= static_cast(s.size()); ++length) {
int current = 0;
if (s[length - 1] != '0') {
current += oneBack;
}
if (validPair(s[length - 2], s[length - 1])) {
current += twoBack;
}
twoBack = oneBack;
oneBack = current;
}
return oneBack;
}
public:
int numDecodings(std::string s) {
return rollingDp(s);
}
};
解题思路
--------
递归切分
~~~~~~~~
从下标 ``index`` 开始,下一段编码只有两种长度:
* 当前字符不是 ``0`` 时,可以把它作为一位编码,递归处理 ``index + 1``;
* 当前两位处于 ``10..26`` 时,可以把它们作为两位编码,递归处理 ``index + 2``。
到达字符串末尾表示此前所有字符都已被合法切分,因此返回 1。遇到 ``0`` 则当前后缀无法从一位编码开始,返回 0。
同一个后缀会被不同切分路径重复计算。例如处理 ``1212`` 时,下标 2 既可能由 ``1|2`` 到达,也可能由 ``12`` 到达,
裸递归因此最坏呈指数增长。
后缀记忆化
~~~~~~~~~~
``memo[index]`` 保存后缀 ``s[index:]`` 的解码方案数。状态只由起始下标决定,因为此前如何切分不会改变剩余字符。
每个下标首次计算后写入缓存,后续直接复用,把重复递归压缩为线性数量的状态。
前缀动态规划
~~~~~~~~~~~~
定义 ``dp[length]`` 为前 ``length`` 个字符的完整解码方案数。最后一个编码只能占一位或两位:
.. code-block:: text
s[length-1] 可以单独解码
dp[length] += dp[length-1]
s[length-2:length] 属于 10..26
dp[length] += dp[length-2]
两类方案的最后一个编码长度不同,因此互不重复。任意完整解码也必然以其中一种编码结束,所以转移没有遗漏。
空前缀状态
~~~~~~~~~~
``dp[0] = 1`` 表示空前缀只有一种空切分。它让首个合法一位编码从 ``dp[0]`` 获得一个方案,也让前两个字符组成
合法两位编码时从 ``dp[0]`` 获得一个方案。
零的约束
~~~~~~~~
字符 ``0`` 会同时限制两条转移:
* 当前字符为 ``0`` 时,不能接收 ``dp[length-1]`` 的一位贡献;
* 只有 ``10`` 或 ``20`` 才能接收 ``dp[length-2]`` 的两位贡献。
因此 ``06`` 从首字符开始就是 0 种方案,``30`` 的两条转移都无效,而 ``10`` 恰好只保留 ``10`` 这一种切分。
状态演化
~~~~~~~~
以 ``11106`` 为例:
.. list-table::
:header-rows: 1
* - 前缀
- 一位贡献
- 两位贡献
- 方案数
* - 空
- —
- —
- 1
* - ``1``
- 1
- —
- 1
* - ``11``
- 1
- 1
- 2
* - ``111``
- 2
- 1
- 3
* - ``1110``
- 0
- 2
- 2
* - ``11106``
- 2
- 0
- 2
滚动压缩
~~~~~~~~
计算 ``dp[length]`` 只依赖 ``dp[length-1]`` 和 ``dp[length-2]``。用 ``oneBack``、``twoBack`` 保存这两个状态,
先算出 ``current``,再整体向前滚动,即可把额外空间从 ``O(n)`` 降为 ``O(1)``。
复杂度
~~~~~~
裸递归最坏为指数时间,递归深度 ``O(n)``。记忆化搜索和两种动态规划均为 ``O(n)`` 时间;记忆化与完整表使用
``O(n)`` 空间,滚动动态规划使用 ``O(1)`` 额外空间。