## Decode Ways

###### DESCRIPTION (credit Leetcode.com)

Your are given a string s containing only digits. Write a function to return the number of ways to decode using the following mapping:

```
'1' -> "A"
'2' -> "B"
'3' -> "C"
...
'26' -> "Z"
```

There may be multiple ways to decode a string. For example, "14" can be decoded as "AD" or "N".

###### EXAMPLES

Input:

`s = 101`

Output:

`1`

Explanation: The only way to decode it is "JA". "01" cannot be decoded into "A" as "1" and "01" are different.

Run your code to see results here

## Explanation

This solution uses a **botton-up dynamic programming** approach to solve the problem. We'll walkthrough how the solution solves the problem when the input string is s = 11106.

We create an integer array dp of length n + 1 where n is the length of the input string s. dp[i] is equal to the number of ways to decode the first i characters of the string s. If the first character of the string is 0, we can return 0 immediately. Otherwise, we initialize dp[0] = 1 (there is one way to decode an empty string) and dp[1] = 1 (one way to decode the first character of s).

def num_decodings(s):if not s or s[0] == '0':return 0n = len(s)dp = [0] * (n + 1)dp[0], dp[1] = 1, 1for i in range(2, n + 1):digit = int(s[i - 1])if digit != 0:dp[i] += dp[i - 1]digit = int(s[i - 2:i])if 10 <= digit <= 26:dp[i] += dp[i - 2]return dp[n]

We then use a for-loop i which goes from 2 to n to iterate through the string. The body of each loop determines the correct value of dp[i] by looking at the previous two characters of the string.

#### Single Digit

We first check the ith digit of the string. If it is not equal to 0, then the number of ways we to decode the first i characters of the string is equal to the number of ways to decode the first i - 1 characters of the string (each of those ways and the encoding of the ith digit). This allows us to set dp[i] = dp[i - 1].

def num_decodings(s):if not s or s[0] == '0':return 0n = len(s)dp = [0] * (n + 1)dp[0], dp[1] = 1, 1for i in range(2, n + 1):digit = int(s[i - 1])if digit != 0:dp[i] += dp[i - 1]digit = int(s[i - 2:i])if 10 <= digit <= 26:dp[i] += dp[i - 2]return dp[n]

When it is equal to 0, it's not possible to decode the ith digit alone, so we leave dp[i] as 0 and continue.

def num_decodings(s):if not s or s[0] == '0':return 0n = len(s)dp = [0] * (n + 1)dp[0], dp[1] = 1, 1for i in range(2, n + 1):digit = int(s[i - 1])if digit != 0:dp[i] += dp[i - 1]digit = int(s[i - 2:i])if 10 <= digit <= 26:dp[i] += dp[i - 2]return dp[n]

#### Double Digit

Next, we move onto checking the ith and ith - 1 digits together. If they form a number between 10 and 26 (inclusive), then we can decode the ith and ith - 1 digits together. This means we have an additional dp[i - 2] ways to decode the first i characters of the string (each of those ways and the encoding of the ith and ith - 1 digits). This allows us to set dp[i] += dp[i - 2].

def num_decodings(s):if not s or s[0] == '0':return 0n = len(s)dp = [0] * (n + 1)dp[0], dp[1] = 1, 1for i in range(2, n + 1):digit = int(s[i - 1])if digit != 0:dp[i] += dp[i - 1]digit = int(s[i - 2:i])if 10 <= digit <= 26:dp[i] += dp[i - 2]return dp[n]

Finally, we return dp[n] which is the number of ways to decode the entire string.

## Solution

def num_decodings(s):if not s or s[0] == '0':return 0n = len(s)dp = [0] * (n + 1)dp[0], dp[1] = 1, 1for i in range(2, n + 1):digit = int(s[i - 1])if digit != 0:dp[i] += dp[i - 1]digit = int(s[i - 2:i])if 10 <= digit <= 26:dp[i] += dp[i - 2]return dp[n]

## Complexity Analysis

**Time Complexity**: O(n) - We iterate through the string once.
**Space Complexity**: O(n) - We use an array of length n + 1 to store the number of ways to decode the first i characters of the string.

Loading comments...