Python, DP with table look up


  • 2
    Y

    We know the DP, let dp[i] is the total ways of decoding for ith position of a string,function is dp[i]=digit1 * dp[i-1]+digit2 * dp[i-2],where digit1 is the ways of only 1 digit at the its position, digit2 is the ways of the decoding of only 2 digits at pos i and i-1,for the digit1, it is clear and simple: "*"->9, "0"->0, "1"-"9"->1, for the digit2, there are some combinations, to simply this, use a table to look up.

                     S[i]   "*"  "0"  "1"-"6"  "7"-"9"
             s[i-1]     |---------------------------------
              "*"       |   15    2      2        1     
              "1"       |   9     1      1        1       
              "2"       |   6     1      1        0     
            "0","3"-"9" |   0     0      0        0    
    

    so we create such a table, then look up the table for the ways of 2 digits only

        def numDecodings(self, s):
            """
            :type s: str
            :rtype: int
            """
            table2=[[15,2,2,1],[9,1,1,1],[6,1,1,0]]
            table2Colmap={"*":0,"0":1,"1":2,"2":2,"3":2,"4":2,"5":2,"6":2,"7":3,"8":3,"9":3}
    
            def get_1digit_ways(si):
                if si=="0": ans=0
                else:
                    ans=9 if si=="*" else 1
                return ans
    
            def get_2digit_ways(table2,table2Colmap,si_1,si):
                ans=0
                if si_1=="0" or "3"<=si_1<="9":
                    ans=0
                else:
                    i=0 if si_1=="*" else  ord(si_1)-ord("0")
                    j=table2Colmap[si]
                    ans=table2[i][j]
                return ans
    
            n = len(s)
            mod=1000000007
            if n==0 or s[0]=="0": return 0
    
            dp1=get_1digit_ways(s[0])
            if n==1: return dp1
            dp2_digt1ways=get_1digit_ways(s[1])
            dp2_digt2ways=get_2digit_ways(table2,table2Colmap,s[0],s[1])
    
            dp2=dp1*dp2_digt1ways+dp2_digt2ways
            if n==2: return dp2
            for i in xrange(2,n):
                digit1=get_1digit_ways(s[i])
                digit2=get_2digit_ways(table2,table2Colmap,s[i-1],s[i])
    
                dp=(dp2*digit1%mod + dp1*digit2%mod)%mod
                dp2,dp1=dp,dp2
            return dp
    

  • 0
    E

    Nicely done, great table aswell!


Log in to reply
 

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