Decode Ways
franklinqin0 StringDP
# Solution
Both solutions take linear runtime.
# Iterative DP
# Linear Space
def numDecodings(self, s: str) -> int:
if not s:
return 0
dp = [0 for _ in range(len(s) + 1)]
dp[0] = 1
if s[0] != '0':
dp[1] = 1
for i in range(2, len(dp)):
if s[i-1] != '0':
dp[i] += dp[i-1]
two_digits = int(s[i-2:i])
if two_digits >= 10 and two_digits <= 26:
dp[i] += dp[i-2]
return dp[len(s)]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# Constant Space
def numDecodings(self, s: str) -> int:
if not s:
return 0
fst, snd = 1, 0
if s[0] != '0':
snd = 1
for i in range(2, len(s) + 1):
temp = snd
if s[i-1] == '0':
snd = 0
two_digits = int(s[i-2:i])
if two_digits >= 10 and two_digits <= 26:
snd += fst
fst = temp
return snd
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17