classSolution(object):defnumDecodings(self,s):""" :type s: str :rtype: int """code=['10','11','12','13','14','15','16','17','18','19','20','21','22','23','24','25','26']ifs==""ors[0]=='0':return0dp=[0forxinrange(len(s)+1)]dp[0]=1foriinrange(len(s)):ifs[i]!="0":# exception is '0', since the number of 'X,X,X,0' is 0.dp[i+1]+=dp[i+1-1]# 1.append s[-1] to each item of last layer, number doesn't change.ifs[i-1:i+1]incode:dp[i+1]+=dp[i+1-2]# 2.if the last two digit is in code, add its numberreturndp[len(s)]if__name__=='__main__':answer=Solution()printanswer.numDecodings('101')
近期评论