Decode Ways
一条由大写字母组成的消息按照 A = 1、B = 2 的规则编码，依此类推，直到 Z = 26，并且编码之间没有分隔符。给定数字字符串 s，返回可能生成该字符串的消息数量。
一个字母可以由一位数字或相邻的两位数字解码，而且编码不会以 0 开头：06 不代表 6，单独的 0 也不代表任何字母。如果无法解码，返回 0。
函数
- sstring
- 要解码的数字字符串
- 返回值integer
- 编码为 s 的字母消息数量
约束条件
1 ≤ s.length ≤ 100s只包含数字0到9，并且它可能以0开头。- 每个前缀和后缀
s的读法都少于231，因此答案以及计算过程中得到的每个计数都能装入有符号 32 位整数。
示例
- 输入
- s = "2611"
- 输出
- 4
- 解释
- 这四种读法是
2 6 1 1（BFAA）、26 1 1（ZAA）、2 6 11（BFK）和26 11（ZK）。中间的数字不会配对，因为 61 大于 26。
- 输入
- s = "1203"
- 输出
- 1
- 解释
0必须与它前面的2配对，组成20，这样就会得到1 20 3（ATC）。如果先读取12，0就会单独留下，而03以 0 开头。
- 输入
- s = "06"
- 输出
- 0
- 解释
- 首个字母必须以
0开头。单独的0不是字母，而06不是代码，因此没有任何消息会生成这个字符串。
进阶
如果 s 还可能包含 *，表示 1 到 9 中的任意数字，该怎么办？你能否在 O(n) 时间内计算出读法的数量，并对 10^9+7 取模？
提示
逐个打开提示，每个都会多透露一点。
只看第一个数字。第一个字母有多少种读法？每种选择后，字符串还剩下什么？
字符串剩余部分的读取次数只取决于剩余部分从哪里开始，而不取决于你是怎么到达那里的。每个起点只计算一次，并重复使用这个计数。
设
ways(i)表示前i位数字的解读方式数，其中ways(0) = 1。当数字i-1不为0时，加上ways(i-1)；当位置i前的两位数字组成的数在 10 到 26 之间时，加上ways(i-2)。你只需要保留最近的两个计数。
题解
每个数字都可以单独对应一个字母，也可以和相邻数字组合，因此解码方式的数量会像 Fibonacci 数列一样增长：45 个 1 对应 1836311903 种解码方式。逐一列出这些方式是不可能的，但完成解码的方式只取决于到达的位置，所以每个位置只需计算一次。0 只能作为 10 或 20 的结尾。
尝试用递归进行两种读取
结果正确，但无法在最大的测试中运行完毕
思路
在索引 i 处，0 不能开始任何字母，因此这条路径不会产生任何解码结果。否则，读取一位数字，并从 i+1 开始统计剩余部分；如果这两位数字组成 10 到 26 之间的数，也读取这两位，并从 i+2 开始统计。这两种选择对应不同的首字母，因此它们的数量可以相加，且不会重复；到达末尾就完成一种解码结果。
没有记住任何结果，所以这些调用遵循斐波那契规则：45 个 1 大约需要 5 × 10^9 次调用。答案为 0 也不会更快：44 个 1、55 个 3 和最后一个 0 大约需要 10^11 次调用，因为每种只读取这些 1 的解码方式都会在最后一位才失败。
算法
waysFrom(i)统计从索引i开始读取这些数字的方式数。- 到达字符串末尾时，返回 1。遇到
0时，返回 0。 - 否则，返回
waysFrom(i+1)，如果数字i和i+1组成的数不大于 26，则再加上waysFrom(i+2)。 - 答案是
waysFrom(0)。
def numDecodings(s):
n = len(s)
def ways_from(i):
# The number of ways to decode s[i:].
if i == n:
return 1 # nothing left: one finished reading
if s[i] == "0":
return 0 # no letter code starts with 0
ways = ways_from(i + 1) # read one digit
if i + 1 < n and int(s[i:i + 2]) <= 26:
ways += ways_from(i + 2) # read two digits, 10 to 26
return ways
return ways_from(0)使用记忆化的递归
思路
递归会反复提出同一个问题。在 "11111" 中，在处理完 1 1 1、11 1 和 1 11 后，都需要从索引 3 开始的计数；每次得到的计数都相同，因为它只取决于从索引 3 开始的数字。每个计数只需在首次计算时保存，并用 -1 标记尚未计算的项，因为 0 是一个有效的计数。
共有 n 个位置，每个位置只计算一次，且每次计算的工作量都是常数：时间复杂度为 O(n)。记忆表和调用栈占用 O(n) 的空间，调用深度最多为 100。
算法
- 用
-1填充memo，每个索引对应一个槽位。 - 在
waysFrom(i)中，如果到达字符串末尾，就返回 1；如果memo[i]不为-1，就返回memo[i]。 - 否则，像普通递归那样计数，将计数保存到
memo[i]中，即使计数为 0 也要保存，然后返回它。
def numDecodings(s):
n = len(s)
memo = [-1] * n # memo[i]: ways to decode s[i:], -1 until worked out
def ways_from(i):
if i == n:
return 1
if memo[i] != -1:
return memo[i]
ways = 0
if s[i] != "0":
ways = ways_from(i + 1) # read one digit
if i + 1 < n and int(s[i:i + 2]) <= 26:
ways += ways_from(i + 2) # read two digits, 10 to 26
memo[i] = ways
return ways
return ways_from(0)使用两个计数器自底向上
思路
改为统计前缀。令 ways(i) 表示前 i 位数字的解码方式数。最后一个字母可以只对应数字 i-1，该数字必须在 1 到 9 之间，此时有 ways(i-1) 种解码方式；也可以对应数字 i-2 和 i-1，这两个数字必须组成 10 到 26，此时有 ways(i-2) 种解码方式。把符合条件的部分相加。空前缀有一种解码方式，所以 ways(0) = 1。
对于 "1203"，计数依次为 1、2，然后在 0 处回到 1，因为只有 20 有效，它会沿用 2 之前的计数。3 单独解码，因此计数仍为 1。每个计数只需查看前两个位置，所以用两个变量代替表格：时间复杂度为 O(n)，空间复杂度为 O(1)。
算法
- 将
twoBack = 0和oneBack = 1设为初始值，它们表示空前缀的计数。 - 对于每个索引
i，如果数字i不是0，就将current设为oneBack，否则设为 0。 - 如果
i ≥ 1、数字i-1不是0，并且数字i-1和i组成的数不超过 26，就加上twoBack。 - 向前移动：将
twoBack = oneBack，然后将oneBack = current。 - 返回
oneBack。
def numDecodings(s):
# ways(i) counts the readings of the first i digits; ways(0) = 1.
two_back, one_back = 0, 1 # ways(i-1) and ways(i) before digit i is read
for i in range(len(s)):
current = 0
if s[i] != "0":
current = one_back # digit i is a letter on its own
if i >= 1 and s[i - 1] != "0" and int(s[i - 1:i + 1]) <= 26:
current += two_back # digits i-1 and i form one letter, 10 to 26
two_back, one_back = one_back, current
return one_back
易错点和边界情况
- 把
0当作字母，或把06当作 6。"30"、"100"和"06"的读法都为 0 种。 - 只用
≤ 26检查两位数片段。05作为数字是 5，但不是有效编码，所以要检查它的首位是否不为0。 - 用 0 标记未知的记忆槽位。读法为 0 的位置就不会被视为已存储：对于 44 个 1、55 个 3 和最后一个
0，调用次数又会回到约10^11次。 - 读取索引 0 之前的数字。用
i ≥ 1为两位数检查添加保护条件；在 Python 中，s[-1]会悄悄读取最后一位数字。 - 把
s转成一个数字。一百位数字无法放进任何整数类型，而且会丢失影响答案的前导零。
常见问题3
Decode Ways 的时间复杂度是多少？
自底向上的解法只需读取每个数字一次，且每次操作的耗时恒定：时间复杂度为 O(n)，额外空间复杂度为 O(1)。记忆化递归的时间复杂度也是 O(n)，但空间复杂度为 O(n)。普通递归的时间复杂度是指数级的：对于由 1 组成的字符串，调用次数会以 1.618^n 的速度增长。
Decode Ways 和 Climbing Stairs 有什么关系？
这两种方法都在计算用长度为 1 和 2 的步长覆盖一条线的方式数。在 Climbing Stairs 中，每一步都可以走，因此计数结果是斐波那契数。在 Decode Ways 中，走一步需要满足数字为 1 到 9，走两步需要满足数字为 10 到 26，因此只有满足条件时才会加上对应的项。
在 Decode Ways 中，如何处理 0？
0 本身不能单独表示一个字母，因此必须和它前面的数字配对，组成 10 或 20。只有当它前面是 1 或 2 时，它才会加上往前数两位的数字所对应的计数，否则不会增加。开头是 0、连续出现两个 0，或 3 到 9 后面跟着 0，结果都是 0。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def numDecodings(s):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
s = "2611"
预期输出
4