### The Problem

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.

Check LeetCode link for more details and example input & output.

### A Recursive Solution

Below is a straightforward recursive solution.

``````  public int numDecodings(String s) {
return numberOfDecodingStartAt(s, 0);
}

int numberOfDecodingStartAt(String s, int index) {
if (index == s.length()) {
return 1;
}

int result = 0;
if (isChar(s, index, index + 1)) {
result += numberOfDecodingStartAt(s, index + 1);
}
if (index + 2 <= s.length() && isChar(s, index, index + 2)) {
result += numberOfDecodingStartAt(s, index + 2);
}
return result;
}

boolean isChar(String s, int start, int end) {
// "06" cannot be mapped into 'F' since "6" is different from "06".
if (s.charAt(start) == '0') {
return false;
}

int code = Integer.parseInt(s.substring(start, end));
return code > 0 && code < 27; // 1 - 26
}
``````

### Dynamic Programming Solutions

#### A Top Down Approach

Improve the performance by caching the results of sub problems.

``````  public int numDecodings(String s) {
int[] dp = new int[s.length()];
Arrays.fill(dp, -1);

return numberOfDecodingStartAt(s, 0, dp);
}

int numberOfDecodingStartAt(String s, int index, int[] dp) {
if (index == s.length()) {
return 1;
}

if (dp[index] != -1) {
return dp[index];
}

int result = 0;
if (isChar(s, index, index + 1)) {
result += numberOfDecodingStartAt(s, index + 1, dp);
}
if (index + 2 <= s.length() && isChar(s, index, index + 2)) {
result += numberOfDecodingStartAt(s, index + 2, dp);
}
dp[index] = result;
return result;
}

boolean isChar(String s, int start, int end) {
if (s.charAt(start) == '0') {
return false;
}

int code = Integer.parseInt(s.substring(start, end));
return code > 0 && code < 27; // 1 - 26
}
``````

#### A Bottom Up Approach

`dp[i]` is the sub problem, whose input is the sub string of `s`, starting at the index `i`.

``````  dp[i] = (isChar(s, i, i + 1) ? dp[i + 1] : 0)
+ (isChar(s, i, i + 2) ? dp[i + 2] : 0)
``````

Base cases:

• `dp[s.length() - 1] = isChar(s, s.length() - 1, s.length()) ? 1 : 0`
• `dp[s.length()] = 1`, (Try using `"12"` as the input, you will find `dp[2]` is `1`.)
``````  public int numDecodings(String s) {
int dp1 = isChar(s, s.length() - 1, s.length()) ? 1 : 0; // dp[i+1]
int dp2 = 1; // dp[i+2]

for (int i = s.length() - 2; i >= 0; i--) {
int tmp = 0;
if (isChar(s, i, i + 1)) {
tmp += dp1;
}
if (isChar(s, i, i + 2)) {
tmp += dp2;
}
dp2 = dp1;
dp1 = tmp;
}

return dp1;
}

boolean isChar(String s, int start, int end) {
if (s.charAt(start) == '0') {
return false;
}

int code = Integer.parseInt(s.substring(start, end));
return code > 0 && code < 27; // 1 - 26
}
``````