## 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 = 1
dp = 0 if s == "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.