Decode ways#

Levels: level-4

Data structures: string

Practice Link#

Description#

A message containing letters from A-Z is being encoded to numbers using the following mapping:
```
1'A' -> 1
2'B' -> 2
3...
4'Z' -> 26
```
Given a non-empty string containing only digits, determine the total number of ways to decode it.

Examples#

1Input: "12"
2Output: 2
3Explanation: It could be decoded as "AB" (1 2) or "L" (12).

1Input: "226"
2Output: 3
3Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Python Solution#

 1class Solution:
 2    def numDecodings(self, s):
 3        if not s or s[0] == '0':
 4            return 0
 5
 6        dp = [0 for x in range(len(s) + 1)]
 7
 8        # base case initialization
 9        dp[0:2] = [1, 1]
10
11        for i in range(2, len(s) + 1):
12            # One step jump
13            if 0 < int(s[i - 1:i]):  #(2)
14                dp[i] = dp[i - 1]
15            # Two step jump
16            if 10 <= int(s[i - 2:i]) <= 26:  #(3)
17                dp[i] += dp[i - 2]
18
19        return dp[-1]