# 91. Decode Ways
## me, wrong strategy, fail
### try 1, fail
```python=
class Solution:
def numDecodings(self, s: str) -> int:
ints = int(s)
if ints == 0: return 0
if 1 <= ints <= 10: return 1
if 11 <= ints <= 19: return 2
if ints == 10: return 1
if 21 <= ints <= 26: return 2
if 27 <= ints <= 99: return 1
return self.numDecodings(s[0:2]) * self.numDecodings(s[2:]) + self.numDecodings(s[0]) * self.numDecodings(s[1:])
```
:::danger
Wrong Answer
Input
"226"
Output
4
Expected
3
:::
I double count the `2 | 2 | 6`
### try 2, fail
```python=
class Solution:
def numDecodings(self, s: str) -> int:
ints = int(s)
if ints == 0: return 0
if 1 <= ints <= 10: return 1
if 11 <= ints <= 19: return 2
if ints == 10: return 1
if 21 <= ints <= 26: return 2
if 27 <= ints <= 99: return 1
return self.numDecodings(s[0:2]) * self.numDecodings(s[2:]) + self.numDecodings(s[0]) * self.numDecodings(s[1:]) - self.numDecodings(s[0]) * self.numDecodings(s[1]) * self.numDecodings(s[2:])
```
:::danger
Wrong Answer
Input
"01"
Output
1
Expected
0
:::
`"01"` is going the same as `"1"`, which is wrong
### try 3, fail
```python=
class Solution:
def numDecodings(self, s: str) -> int:
if len(s) == 2 and s[0] == "0":
return 0
ints = int(s)
if ints == 0: return 0
if 1 <= ints <= 10: return 1
if 11 <= ints <= 19: return 2
if ints == 10: return 1
if 21 <= ints <= 26: return 2
if 27 <= ints <= 99: return 1
return self.numDecodings(s[0:2]) * self.numDecodings(s[2:]) + self.numDecodings(s[0]) * self.numDecodings(s[1:]) - self.numDecodings(s[0]) * self.numDecodings(s[1]) * self.numDecodings(s[2:])
```
:::danger
Wrong Answer
Input
"012"
Output
2
Expected
0
:::
### try 4, fail
```python=
class Solution:
def numDecodings(self, s: str) -> int:
if s[0] == "0":
return 0
ints = int(s)
if ints == 0: return 0
if 1 <= ints <= 10: return 1
if 11 <= ints <= 19: return 2
if ints == 10: return 1
if 21 <= ints <= 26: return 2
if 27 <= ints <= 99: return 1
return self.numDecodings(s[0:2]) * self.numDecodings(s[2:]) + self.numDecodings(s[0]) * self.numDecodings(s[1:]) - self.numDecodings(s[0]) * self.numDecodings(s[1]) * self.numDecodings(s[2:])
```
:::danger
Wrong Answer
Input
"230"
Output
1
Expected
0
:::
### try 5, fail
```python=
class Solution:
def numDecodings(self, s: str) -> int:
if s[0] == "0":
return 0
ints = int(s)
if ints == 0: return 0
if 1 <= ints <= 10: return 1
if 11 <= ints <= 19: return 2
if ints == 10: return 1
if 21 <= ints <= 26: return 2
if ints == 30 or ints == 40 or ints == 50 or ints == 60 or ints == 70 or ints == 80 or ints == 90: return 0
if 27 <= ints <= 99: return 1
return self.numDecodings(s[0:2]) * self.numDecodings(s[2:]) + self.numDecodings(s[0]) * self.numDecodings(s[1:]) - self.numDecodings(s[0]) * self.numDecodings(s[1]) * self.numDecodings(s[2:])
```
:::danger
Runtime Error
Details
Playground Debug
RecursionError: maximum recursion depth exceeded while calling a Python object
Line 3 in numDecodings (Solution.py)
[Previous line repeated 996 more times]
Line 14 in numDecodings (Solution.py)
Line 14 in numDecodings (Solution.py)
Line 14 in numDecodings (Solution.py)
stdout
12120
12
120
12
0
1
20
20
20
20
20
20
20
... 49910 more lines
Last executed input
"12120"
:::
It is a typo.
Should be
`if ints == 10: return 1`
Not
`if ints == 20: return 1`
### try 6, fail
```python=
class Solution:
def numDecodings(self, s: str) -> int:
print(s)
if s[0] == "0":
return 0
ints = int(s)
if ints == 0: return 0
if 1 <= ints <= 10: return 1
if 11 <= ints <= 19: return 2
if ints == 20: return 1
if 21 <= ints <= 26: return 2
if ints == 30 or ints == 40 or ints == 50 or ints == 60 or ints == 70 or ints == 80 or ints == 90: return 0
if 27 <= ints <= 99: return 1
return self.numDecodings(s[0:2]) * self.numDecodings(s[2:]) + self.numDecodings(s[0]) * self.numDecodings(s[1:]) - self.numDecodings(s[0]) * self.numDecodings(s[1]) * self.numDecodings(s[2:])
```
:::danger
Time Limit Exceeded
Last executed input
"6065812287883668764831544958683283296479682877898293612168136334983851946827579555449329483852397155"
:::
### try 7, fail
```python=
class Solution:
def numDecodings(self, s: str) -> int:
if s[0] == "0":
return 0
ints = int(s)
if ints == 0: return 0
if 1 <= ints <= 10: return 1
if 11 <= ints <= 19: return 2
if ints == 20: return 1
if 21 <= ints <= 26: return 2
if ints == 30 or ints == 40 or ints == 50 or ints == 60 or ints == 70 or ints == 80 or ints == 90: return 0
if 27 <= ints <= 99: return 1
return (self.numDecodings(s[0:2]) - self.numDecodings(s[0])*self.numDecodings(s[1]))*self.numDecodings(s[2:]) + self.numDecodings(s[0])*self.numDecodings(s[1:])
```
:::danger
Time Limit Exceeded
Last executed input
"6065812287883668764831544958683283296479682877898293612168136334983851946827579555449329483852397155"
:::
:::info
I shoud have memory
I should DP
:::
## dp
### try 1, fail
```python=
class Solution:
def numDecodings(self, s: str) -> int:
if s[0] == "0":
return 0
# the first char is not '0'
n = len(s)
dp = [0] * n # 0 ~ n-1
dp[0] = 1
for i in range(1, n):
if s[i] != '0':
dp[i] = dp[i-1]
if 10 <= int(s[i-1:i+1]) <= 26: # i-1 ~ i
dp[i] += 1
return dp[-1]
```
:::danger
Wrong Answer
Input
"12120"
Output
1
Expected
3
:::
### try 2, success, use `if` in `for` to deal with the special case of counting `s[0:3]`
```python=
def numDecodings(self, s: str) -> int:
if s[0] == "0":
return 0
# the first char is not '0'
n = len(s)
dp = [0] * n # 0 ~ n-1
dp[0] = 1
for i in range(1, n):
print(dp)
if s[i] != '0':
dp[i] += dp[i-1]
if 10 <= int(s[i-1:i+1]) <= 26: # i-1 ~ i
# to avoid access of dp[-1]
if i == 1 :
dp[i] += 1
else:
dp[i] += dp[i-2]
print(dp)
return dp[-1]
```
### try 3, success, shift dp chart to avoid `dp[0:3]`
```python=
def numDecodings(self, s: str) -> int:
if s[0] == "0": #
return 0
# the first char is not '0'
n = len(s)
dp = [0] * (n+1) # 0 ~ n
# we shift the dp chart from the input s by 1
# the possible decode way of s[0:a+1] is stroe at dp[a+1]
dp[0] = 1 # only for counting the 2-digit at s[0~1],
dp[1] = 1 # for the first char is not '0', there is one decode way
for i in range(2, n+1):
# if the 1-digit is 1~9 then the previous count is OK to use
if s[i-1] != '0':
dp[i] += dp[i-1]
# if the 2-digit is 10~26, then the previous count is OK to use
if 10 <= int(s[i-2:i]) <= 26:
dp[i] += dp[i-2]
return dp[n]
```
Sign in with Wallet
Connect another wallet