Share original Python 1D DP code


  • 0
    W
    class Solution(object):
        def numDecodings(self, s):
            """
            :type s: str
            :rtype: int
            """
            st=list(s)
            n=len(st)
            if n==0:
                return 0
            elif n==1 and s !='0':
                return 1
            re=[0 for i in range(n)]
            if st[0]=='0':
                re[0]=0
                return 0
            else:
                re[0]=1
            if st[1]=='0' and st[0] in ['1','2']:
                re[1]=1
            elif st[1]=='0' and st[0] not in ['1','2']:
                re[1]=0
            elif st[1] in ['1','2','3','4','5','6'] and st[0] in ['1','2']:
                re[1]=2
            elif st[1] in ['7','8','9'] and st[0] in ['1']:
                re[1]=2
            else:
                re[1]=1
            for i in range(n-2):
                if st[i+2]=='0' and st[i+1] in ['1','2']:
                    re[i+2]=re[i]
                elif st[i+2]=='0' and st[i+1] not in ['1','2']:
                    re[i+2]=0
                elif st[i+2] in ['1','2','3','4','5','6'] and st[i+1] in ['1','2']:
                    re[i+2]=re[i+1]+re[i]
                elif st[i+2] in ['7','8','9'] and st[i+1] in ['1']:
                    re[i+2]=re[i+1]+re[i]
                else:
                    re[i+2]=re[i+1]
            return re[n-1]

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.