# LeetCode 91. Decode Ways

## The Problem

Link to original problem on Leetcode.

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 test cases are generated so that the answer fits in a **32-bit** integer.

## Examples

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 = "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).

## My Solution

This is a dynamic programming problem. It needs to be solved by breaking the problem down into sub-problems. We can do it either recursively or iteratively.

### Recursion with Memoization

To solve this recursively, we will call the function again and again with smaller sub-sections of the original string until we trigger a base case. Here, we’ll assume that an empty string means we’ve found a correct decoding and to return `1`

. If at any point the string starts with `"0"`

, we know it can’t be properly mapped and return `0`

. These smaller sub-strings will be memoized in out `memo`

variable, so that we don’t waste resources recomputing things we’ve seen before.

```
// We modify the function to accept a Map named memo. We'll
// use this to cache previously seen strings that we've
// decoded. It's initialized to an empty Map.
function numDecodings(
s: string,
memo: Map<string, number> = new Map(),
): number {
// Base case: if the string is empty, we've found 1 way.
if (s === '') return 1;
// If the string has a leading zero, it cannot have any
// successful mapping, so return 0.
if (s.slice(0, 1) === '0') return 0;
// Don't recompute if we've seen this string before. Just
// return what's in our map.
if (memo.has(s)) return memo.get(s);
// We'll initialize variables to analyze the pieces of the
// string that would be either a single digit to letter
// decoding, or a two digit number to letter decoding.
let singleDigit = 0,
doubleDigit = 0;
// For single digit decodings, we need to know that the number
// is between 1 and 9 inclusive. If so, we recursively call
// the function on the rest of the string after this single
// digit. If there was only one letter in the string left,
// we'd be calling with an empty string and get our base case
// returned.
if (1 <= +s.slice(0, 1) && 9 >= +s.slice(0, 1)) {
singleDigit = numDecodings(s.slice(1), memo);
}
// For double digit decodings, our two letters of the string
// must parse as an int between 10 and 26 inclusive. If it
// does, we call the function again with the rest of
// the string after those two letters.
if (10 <= +s.slice(0, 2) && 26 >= +s.slice(0, 2)) {
doubleDigit = numDecodings(s.slice(2), memo);
}
// To prevent needless recalculation of repeating sequences in
// the string, save the evaluations to our Map.
memo.set(s, singleDigit + doubleDigit);
// Finally, return the memoized value of the string.
return memo.get(s);
}
```

### Solving Iteratively with Dynamic Programming

The iterative solution is, in my opinion, easier to understand. We create an array `dp`

to hold a running count of valid decodings. We will iterate through the string `s`

, examining the integer values of the previous character and the pair of previous two characters. (We initialized `dp[0]`

and `dp[1]`

to make sure we don’t go out of range when we do this.)

If the currently examined sub-string matches the conditions for either the single- or double-digit decoding, we add to `dp[i]`

the previous value of `dp`

for either single- or double-digits. So if we’re looking at single-digits, and `+s.slice(i - 1, i)`

meets the criteria, then `dp[i]`

will have the value of `dp[i - 1]`

added to it. It’s important that we’re adding to an existing value, not setting it equal to the value, because we’re going to be modifying any given `dp[i]`

multiple times as we check for both valid single- and double-digit decodings.

As we go through the string, values of `dp[i]`

ought to increase as `i`

increased and we find ever more valid decodings. Finally, `dp[s.length]`

will have the total number of valid decodings for the string `s`

.

```
function numDecodings(s: string): number {
if (s === '') return 0;
// Initialize dp as an array with length equal to 1 plus the
// length of the string, all values set to zero.
const dp: number[] = Array.from({ length: s.length + 1 }, () => 0);
// We initialize our dp cache's first two values. dp[0] is 1,
// and this is what we'll add to dp[2] if our first double-
// digit check is valid. dp[1] is either 0 or 1, depending on
// the first character of s. Since leading zeroes aren't
// valid, then we only initialize dp[1] = 1 if there is no
// leading zero. This is the value that will be added to dp[2]
// if the first single-digit decoding validates.
dp[0] = 1;
if (s.charAt(0) !== '0') dp[1] = 1;
for (let i = 2; i <= s.length; i++) {
// For deciding dp[i], we look back at the previous 1 and 2
// characters of s to see if they are valid encodings for
// a letter.
const singleDigit = +s.slice(i - 1, i);
const doubleDigit = +s.slice(i - 2, i);
// If the single-digit encoding is valid, dp[i] should have
// the value of dp[i - 1] added to it.
if (1 <= singleDigit && 9 >= singleDigit) {
dp[i] += dp[i - 1];
}
// Now we also add dp[i - 2] to dp[i] if the double-digit
// encoding is valid.
if (10 <= doubleDigit && 26 >= doubleDigit) {
dp[i] += dp[i - 2];
}
}
// Finally, the last value of dp has the total number of valid
// encodings.
return dp[s.length];
}
```