1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
    def solve(self, nums: str) -> int:
        """
            计算给定字符串译码的可能数
        """
        # 步骤1：特殊处理0、10、20的情况
        if nums == "0":
            return 0
        if nums == "10" or nums == "20":
            return 1
        
        # 以及这种特殊情况：首位为0或者当0的前面不是1或2时，无法译码，0种
        if nums[0] == "0":
	        return 0
        for i in range(1, len(nums)):
            if nums[i] == "0":
                if nums[i - 1] != "1" and nums[i - 1] != "2":
                    return 0

        # 步骤2：开始求解
        dp = [1 for i in range(len(nums) + 1)] # 辅助数组初始化为1
        for i in range(2, len(nums) + 1):
            # nums[i - 2:i]在11-19，21-26之间的情况
            if (nums[i - 2] == "1" and nums[i - 1] != "0") or (
                nums[i - 2] == "2" and nums[i - 1] > "0" and nums[i - 1] < "7"
            ):
                dp[i] = dp[i - 1] + dp[i - 2]
			elif nums[i-1]== 0 and (nums[i - 2] == "1" or nums[i - 2] == "2"):
                dp[i] = dp[i - 2]
            else:
                dp[i] = dp[i - 1]
        return dp[len(nums)]

注意：

  1. 一个数字，要么单独译码，要么两个一起译码，不存在三个视为整体译码，因为只有1-26对应了字母
  2. 只要出现x0，但x不是1或2，比如00、30、40、…就无法译码，因为如果是00，无论分成0和0还是00直接译码都没有对应的整数，拼接再多也没法译码；30也是，因为30本身以及0都无法译码，拼接更多数不会解决问题
    解释：
    nums[i - 2:i] 在11-19，21-26之间的情况， 此时，最后两位可以一起译码，包括几种情况
  • 最后一位单独译码：dp[i - 1] 种可能
  • 最后两位一起译码：dp[i - 2]种可能
    nums[i - 2:i]是10和20时，只能将最后两位一起译码：
  • 最后两位一起译码：dp[i - 2]种可能
    由于不能译码已经排除，所以这里省略这种情况

不能译码的情况：存在0但是不是10和20，也就是前一个数字不是1或2，或者前面根本没有字母，比如”0”,”02”