091._decode_ways.md

###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]