LC 0091 [M] Decode Ways - ALawliet/algorithms GitHub Wiki
prereq: Climbing Stairs
first if statement is a little tricky until you realize at i=2 where s[i-1]='3', because of the +1 padding we actually check T[i-1] (or s-1-1) = T[1] (or s[0]) = include num ways of '2'
T[i] = is the num ways of s up to len i
for the current cell = we add the num ways to make the string 1 indexes before it + 2 indexes before it
s = "231"
i=0: extra base offset. dp[0] = 1
i=1: # of ways to parse "2" => dp[1] = 1
i=2: # of ways to parse "23" => "2" and "23", dp[2] = 2
i=3: # of ways to parse "231" => "2 3 1" and "23 1" => dp[3] = 2
[2 3 1](/ALawliet/algorithms/wiki/2-3-1)
[1 1 0 0](/ALawliet/algorithms/wiki/1-1-0-0)
i=2 s[i-1]=3 T[i-1]=1 s[i-2:i]=23 T[i-2]=1
i=3 s[i-1]=1 T[i-1]=2 s[i-2:i]=31 T[i-2]=1
[1 1 2 2](/ALawliet/algorithms/wiki/1-1-2-2)
class Solution:
def numDecodings(self, s: str) -> int:
dp = {len(s) : 1} # if last pos in string just return 1
def dfs(i):
if i in dp:
return dp[i]
if s[i] == '0':
return 0
res = dfs(i+1)
if (i + 1 < len(s) and (s[i] == '1' or s[i] == '2' and s[i+1] in '0123456')): # int(s[i] + s[i+1]) <= 26)
res += dfs(i + 2)
dp[i] = res
return res
return dfs(0)
import numpy
import string
class Solution:
def numDecodings(self, s: str) -> int:
if not s: return 0
print(' ', numpy.matrix(list(map(int, s))))
T = [0 for i in range(len(s) + 1)]
T[0] = 1
if s[0] != '0':
T[1] = 1
# print(numpy.matrix(T))
# 0 1 2 3
# 2 3 1
# 1 1 0 0
for i in range(2, len(s) + 1):
# print(f'i={i} s[i-1]={s[i-1]} T[i-1]={T[i-1]} s[i-2:i]={s[i-2:i]} T[i-2]={T[i-2]}')
# if 0 < int(s[i-1:i]) <= 9:
if s[i-1] != '0':
T[i] += T[i-1]
if 10 <= int(s[i-2:i]) <= 26:
T[i] += T[i-2]
# print(numpy.matrix(T))
return T[-1]
What if we wanted to print the strings we can make too?
import numpy
import string
letters = dict()
for i in range(len(string.ascii_uppercase)):
letters[i+1] = string.ascii_uppercase[i]
s = '12'
T = [0 for i in range(len(s) + 1)]
U = [[] for i in range(len(s) + 1)]
T[0] = 1
if s[0] != '0':
T[1] = 1
U[1].append(letters[int(s[0])])
for i in range(2, len(s) + 1):
if s[i-1] != '0':
T[i] += T[i-1]
U[i] += U[i-1]
U[i][0] += letters[int(s[i-1])]
if 10 <= int(s[i-2:i]) <= 26:
T[i] += T[i-2]
U[i] += letters[int(s[i-2:i])]
print(numpy.matrix(T))
print(numpy.matrix(U))
print(U[-1])
# => ['AB', 'L']