# LeetCode - Decode Ways

## Problem statement

A message containing letters from *A-Z* can be **encoded** into numbers using the following mapping:

```
'A' -> '1'
'B' -> '2'
...
'Z' -> '26'
```

To **decode** an encoded message,
all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways).
For example, *'11106'* can be mapped into:

```
'AAJF' with the grouping (1 1 10 6)
'KJF' with the grouping (11 10 6)
```

Note that the grouping (1 11 06) is invalid because '06' cannot be mapped into 'F' since '6' is different from '06'.

Given a string *s* containing only digits, *return the number of ways to decode it*.

The answer is guaranteed to fit in a 32-bit integer.

Problem statement taken from: https://leetcode.com/problems/decode-ways

**Example 1:**

```
Input: s = '12'
Output: 2
Explanation: '12' could be decoded as 'AB' (1 2) or 'L' (12).
```

**Example 2:**

```
Input: s = '226'
Output: 3
Explanation: '226' could be decoded as 'BZ' (2 26), 'VF' (22 6), or 'BBF' (2 2 6).
```

**Example 3:**

```
Input: s = '0'
Output: 0
Explanation: There is no character that is mapped to a number starting with 0.
The only valid mappings with 0 are 'J' -> '10' and 'T' -> '20', neither of which start with 0.
Hence, there are no valid ways to decode this since all digits need to be mapped.
```

**Example 4:**

```
Input: s = '06'
Output: 0
Explanation: '06' cannot be mapped to 'F' because of the leading zero ('6' is different from '06').
```

**Constraints:**

```
- 1 <= s.length <= 100
- s contains only digits and may contain leading zero(s).
```

### Explanation

#### Brute force solution

A naive approach is to generate all possible combinations and count the number of correct sequences.

This approach is easy to implement but has time complexity of
**O(2^N)**.

#### Dynamic programming

The problem can be solved using dynamic programming approach.

Let's take the string **'12'**. We can decode the string in 2 ways
**[1, 2]** or **12**.
Now lets append *6* at the end of the string.
For the new string the decode ways are
2 + 1 = 3.
2 for the **[1, 2, 3]** or **[12, 3]** and
1 for **[1, 23]**.

We solved the subproblem first and used it's solution to solve bigger problem. Thats nothing but dynamic programming approach.

Let's check the algorithm.

```
- initialize count array: count[n + 1]
- set count[0] = count[1] = 1
- if s[0] == 0 // first character of string is 0
- return 0
- loop for i = 2; i <= n; i++
- set count[i] = 0
// if string is '02' we should not count '02' as a valid case.
// But if the previous char is greater than 0 we set the current index count same
// as the previous index count.
- if s[i - 1] > '0'
- count[i] = count[i - 1]
// if string is '32' it is not possible to map to any character.
// hence we have (i - 2)th index for 1 or 2 and
// if s[i - 2] is 2 we additionally check for (i - 1)th index to
// be less than 7.
- if s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] < '7')
- count[i] += count[i - 2]
- return count[n]
```

#### C++ solution

```
class Solution {
public:
int countWays(string s, int n){
int count[n + 1];
count[0] = 1;
count[1] = 1;
if(s[0] == '0')
return 0;
for(int i = 2; i <= n; i++){
count[i] = 0;
if(s[i - 1] > '0')
count[i] = count[i - 1];
if(s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] < '7')){
count[i] += count[i - 2];
}
}
return count[n];
}
public:
int numDecodings(string s) {
return countWays(s, s.size());
}
};
```

#### Golang solution

```
func numDecodings(s string) int {
count := make([]int, len(s) + 1)
count[0], count[1] = 1, 1
if s[0] == '0' {
return 0
}
for i := 2; i <= len(s); i++ {
if s[i - 1] > '0' {
count[i] = count[i - 1]
}
if s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] < '7') {
count[i] += count[i - 2]
}
}
return count[len(s)]
}
```

#### Javascript solution

```
var numDecodings = function(s) {
let count = [];
count[0] = 1;
count[1] = 1;
for(let i = 2; i <= s.length; i++){
count[i] = 0;
if(s[i - 1] > '0'){
count[i] = count[i - 1];
}
if(s[i - 2] == '1' || (s[i - 2]) == '2' && s[i - 1] < '7'){
count[i] += count[i - 2];
}
}
return count[s.length];
};
```

#### Dry Run

Let's dry-run our algorithm to see how the solution works.

```
Input: s = '226'
Step 1: int count[n + 1]
count[0] = count[1] = 1
Step 2: if s[0] == '0'
'2' == '0'
false
Step 3: loop for i = 2; i <= n;
2 <= 3
true
if s[i - 1] > '0'
s[2 - 1] > '0'
s[1] > '0'
'2' > '0'
true
count[i] = count[i - 1]
count[2] = count[2 - 1]
= count[1]
= 1
if s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] < '7'))
s[2 - 2] == '1'
s[0] == '1'
'2' == '1'
false
s[i - 2] == '2' && s[i - 1] < '7'
s[2 - 2] == '2' && s[2 - 1] < '7'
s[0] == '2' && s[1] < '7'
'2' == '2' && '2' < '7'
true
count[2] = count[i] + count[i - 2]
= count[2] + count[2 - 2]
= 1 + 1
= 2
i++
i = 3
Step 4: loop for i <= n;
3 <= 3
true
if s[i - 1] > '0'
s[3 - 1] > '0'
s[2] > '0'
'6' > '0'
true
count[i] = count[i - 1]
count[3] = count[3 - 1]
= count[2]
= 2
if s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] < '7'))
s[3 - 2] == '1'
s[1] == '1'
'2' == '1'
false
s[i - 2] == '2' && s[i - 1] < '7'
s[3 - 2] == '2' && s[3 - 1] < '7'
s[1] == '2' && s[2] < '7'
'2' == '2' && '6' < '7'
true
count[3] = count[i] + count[i - 2]
= count[3] + count[3 - 2]
= 2 + 1
= 3
i++
i = 4
Step 5: loop for i <= n;
4 <= 3
false
Step 6: return count[n]
count[3] = 3
So the answer we return is 3.
```