091 decode ways
91. Decode Ways
题目： https://leetcode.com/problems/decode-ways/
tag : DP
难度 : Medium
BASE CASE（len(s) = 1 和 len(s) = 2 ）:
直接check
非BASE CASE ：
先令 dp[i] = 0
如果s[i]是可以map的话 -> dp[i] += dp[i-1] 原本的s[0..i]decode方式加上s[i]
如果s[i-1,i]可以map的话 -> dp[i] += dp[i-2] 原本的s[0...i-1]decode方式加上s[i-1,i]
Python代码（可美化）
class Solution(object):
def numDecodings(self, s):
"""
:type s: str
:rtype: int
"""
keys = ['1', '2', '3', '4', '5', '6', '7', '8', '9' ,'10', '11', '12', '13', '14', '15', '16', '17', '18', '19', '20', '21', '22', '23', '24', '25', '26']
values = ['A', 'B','C', 'D', 'E', 'F', 'G','H', 'I', 'J', 'K', 'L', 'M' , 'N', 'O', 'P','Q', 'S', 'R', 'T', 'U','V', 'W', 'X','Y','Z']
numbersToLetters = dict(zip(keys, values))
ways = {}
n = len(s)
for i in range(n):
ways[i] = 0
if n == 0:
return 0
elif n == 1 :
ways[0] = int(s in numbersToLetters)
elif n == 2:
if (s[0] in numbersToLetters) and (s[1] in numbersToLetters):
ways[1] += 1
if (s in numbersToLetters):
ways[1] += 1
else:
#s[0]
ways[0] = int(s[0] in numbersToLetters)
#s[01]
if (s[0] in numbersToLetters) and (s[1] in numbersToLetters):
ways[1] += 1
if (s[:2] in numbersToLetters):
ways[1] += 1
for i in range(2,n):
if s[i] in numbersToLetters:
ways[i] += ways[i-1]
if (s[i-1:i+1] in numbersToLetters):
ways[i] += ways[i-2]
#print(ways[n-1])
return ways[n-1]
