Fork me on GitHub

Decode ways

Posted on

Decode Ways

Analysis

We should utilize the dynamic perogramming, the transfer equation is, suppose result[i] is the number of decoding ways ending at s[i]

result[i] = result[i-1] + result[i-2] (If both s[i-1~ i] and s[i] is valid)

result[i] = result[i-1] (If only s[i] is valid)

Pay attention to the corner case!!!!

Solution

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
27
28
29
30
31
32
33
34
35
36
class Solution:
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        
        length = len(s)

        result = [1 for i in range(length+1)]
        
        if s[0] < '1' or s[0] > '9':
            return 0
        else:
            result[1] = 1 
        
        for index in range(1, length):
            one_digit_number = int(s[index])
            two_digit_number = int(s[index-1:index+1])
            if one_digit_number == 0:
                if not( two_digit_number <= 26 and two_digit_number >= 10):
                    return 0
                else:
                    result[index+1] = result[index - 1]
                    continue
            
            if two_digit_number <= 26 and two_digit_number >= 10:
                result[index+1] = result[index] + result[index-1]
                continue
                
            ##Defualt case
            result[index+1] = result[index]
                
        return result[length]