# Python, DP with table look up

• 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
``````

• Nicely done, great table aswell!

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