LeetCode-91 解码方法

题目链接：91. 解码方法 - 力扣（LeetCode）

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
class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        list_s=list(s)
        n=len(list_s)
        dp=[]
        for i in range(n+1):#初始化列表 创建一个长度为n+1的列表
             dp.append(0)  # 向列表中添加元素 0
        dp[n]=1
        '''可有可无，但是常规的动态规划需要，这里写一下方便理解，本题中每个位置的值只与前面的两个位置有关。而对于最后一个位置（即 s[n-1])，由于它没有后一个数字可以与之拼接，所以其翻译方案数必定就是 1或0。'''
        if list_s[n-1]=='0':# 如果他是0，则没有解码方式
            dp[n-1]=0
        else :
            dp[n-1]=1	#否则解码方式为1

        for i in range(n-2,-1,-1):  #从n-2 到0 递减  递减长度为-1
            if(list_s[i]=='0'):     #遇到0字符 这个字符的编码方式就为0并进入下次循环
                 dp[i]=0
                 continue

            ans1=dp[i+1]          #如果不是0字符则判断是否小于等于26 满足就是 后边第二个的编码数和后边第一个编码数之和，否则就只是后边第一个的编码数
            ans2=0
            if (ord(list_s[i])-48)*10+(ord(list_s[i+1])-48)<=26:
                ans2=dp[i+2]
            dp[i]=ans1+ans2
        #循环完成返回最前边的数的编码数，即总体的编码数
        return dp[0]