Description
A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.
Example 1:
Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
Example 2:
Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
Solutions
给一串数字，找出其能表示的最多字母组合。
1. DP
看例子 226 其实可以拆分成两个部分来看待，取一个字符，看其是否符合要求，如果符合就把其到这个一个字符位置的组合个数算上，如果不符合那就不算，留着零的状态；然后取两个字符采用同样的过程。
class Solution(object):
def numDecodings(self, s):
"""
:type s: str
:rtype: int
"""
if not s:
return 0
dp = [0 for x in range(len(s) + 1)]
# base case initialization
dp[0] = 1
dp[1] = 0 if s[0] == "0" else 1 #(1)
for i in range(2, len(s) + 1):
# One step jump
if 0 < int(s[i-1:i]) <= 9: #(2)
dp[i] += dp[i - 1]
# Two step jump
if 10 <= int(s[i-2:i]) <= 26: #(3)
dp[i] += dp[i - 2]
return dp[len(s)]
# Runtime: 24 ms, faster than 44.72% of Python online submissions for Decode Ways.
# Memory Usage: 11.8 MB, less than 65.22% of Python online submissions for Decode Ways.