91. 解码方法

Difficulty: 中等

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

'A' -> 1
'B' -> 2
...
'Z' -> 26

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：

• "AAJF" ，将消息分组为 (1 1 10 6)
• "KJF" ，将消息分组为 (11 10 6)

注意，消息不能分组为  (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。

题目数据保证答案肯定是一个 32 位 的整数。

示例 1：

输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2：

输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

示例 3：

输入：s = "0"
输出：0
解释：没有字符映射到以 0 开头的数字。
含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。
由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。

示例 4：

输入：s = "06"
输出：0
解释："06" 不能映射到 "F" ，因为字符串含有前导 0（"6" 和 "06" 在映射中并不等价）。

提示：

• 1 <= s.length <= 100
• s 只包含数字，并且可能包含前导零。

Solution

看到这道题的时候直觉告诉我这道题跟复原IP地址很相似，不过用回溯不是一个好的解决办法，看来直觉还不太准。

其实这道题考察的是动态规划，考察动态规划势必就要考虑如何将大问题化解为子问题。

简单复述题意：给定了只包含数字的字符串，然后要求返回字符串能解码的总数，这是大问题，那么如何将大问题化解为小问题呢？

考虑此时有一个指针，当指针指向字符串索引i的位置，想象一下此时有多少种解码可能？此时有且只有两种可能的解码方式：

其一是索引i位置元素自己编码，比如226，当指针指向6这个元素时候，它自己就可以解码为F，前提是该元素是合法的，字符串不能以0开头，只能介于[1,9]；

其二是索引i位置和i-1位置的元素组合构成合法的编码，但是元素的组合必须介于[10,26]，否则不合法，比如还是按照上面举的例子，当指针指向6这个元素时候它还可以和它前面的2一块组合

这两种情形构成了指针在索引i位置结尾的子字符串的所有解码方式，如果我们用dp[n]表示长度为n的字符串所有的解码方式（字符串为空的时候，解码的方法为1，dp[0]=1），那么该字符串的子串的解码方式可以表示为：dp[i] = dp[i-1] + dp[i-2]。

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        dp = [1] + [0] * n
        
        for i in range(1, n + 1):
            if s[i - 1] != '0': # 字符串不能以0开头
                dp[i] += dp[i - 1]
            
            if i > 1 and s[i - 2] != '0' and int(s[i-2:i]) <= 26:
                dp[i] += dp[i - 2]
        return dp[n]