Decode Ways:
A message containing letters fromA-Z
is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message"12"
, it could be decoded as"AB"
(1 2) or"L"
(12).
The number of ways decoding"12"
is 2.
Solution
- state: # of decede ways up till state i. Easy
- Function: how to increment to next state. hard. See code. Best to find it with examples.
- init.
- return. end
what should the middle function be to next state?
class Solution(object):
def numDecodings(self, s):
"""
:type s: str
:rtype: int
"""
if s == None or len(s) == 0 or s[0] == "0":
return 0
# init
n = len(s)
dp = [1] * (n + 1)
# function from top down approach
for i in range(1, n):
# case 1:
if s[i] == "0":
if s[i - 1] == "1" or s[i - 1] == "2":
dp[i + 1] = dp[i - 1]
else:
return 0
# case 2:
elif s[i - 1] != "0" and int(s[i-1:i+1]) <= 26:
dp[i + 1] = dp[i] + dp[i-1]
# case 3:
else:
dp[i + 1] = dp[i]
return dp[-1]