【牛客剑指offer刷题】：Python：46. 把数字翻译成字符串

有一种将字母编码成数字的方式：‘a’->1, ‘b->2’, … , ‘z->26’。

现在给一串数字，返回有多少种可能的译码结果

数据范围：字符串长度满足 0 < n le 900 进阶：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)

输入：“12”
返回值：2

说明：2种可能的译码结果（”ab” 或”l”）

输入：“31717126241541717”
返回值：192

说明：192种可能的译码结果

#
# 解码
# @param nums string字符串 数字串
# @return int整型
#
class Solution:

    def solve(self , nums ):
        # write code here
        if not nums or nums == "0":
            return 0
        dp = [0 for _ in range(len(nums)+1)]
        
        dp[0], dp[1] = 1, 1
        for i in range(2, len(nums)+1):
            tmp = int(nums[i-2:i])
            if nums[i-1] == "0":       # 1.如果当前位置之前的两位数字是10的倍数，那么只有10/20是有效的
                if tmp == 10 or tmp == 20:
                    dp[i] = dp[i-2]
                else:
                    dp[i] = 0
            elif 11 <= tmp <= 26:      # 2.如果当前位置之前的两位数字是 11 - 26 之间， 那么有两种可能
                dp[i] = dp[i-1] + dp[i-2]
            else:                       # 3.其他情况，只有拆分一种可能
                dp[i] = dp[i-1]
        return dp[-1]