Decode Ways
- 1 min read
- LC-Medium
- Dynamic Programming
3 years ago
Memoization Solution
- The reason we return a 1 when i >= len(s) is because we've found a possible way to decode a string
- LISTEN HERE. If at any point in our DFS, we encounter an invalid decoding, we immediately return
- We only count a valid decoding if we can reach the end of the string
| Time | Space | Explanation |
|---|---|---|
O(n) | O(n) |
def numDecodings(self, s: str) -> int:
memo = {}
def dfs(i):
if i in memo:
return memo[i]
if i >= len(s):
return 1
if s[i] == '0':
return 0
ways = dfs(i + 1)
if i + 1 < len(s) and (s[i] == '1' or (s[i] == '2' and s[i + 1] in '0123456')):
ways += dfs(i + 2)
memo[i] = ways
return ways
return dfs(0)