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.

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

Expected time complexity is O(n) where n is the number of characters in the given data i.e.  encoded string.

Solution

Method 1 - Recursion

To begin with, we can think of the solution for the easy cases. Suppose string is 1 letter word like: 3 . Then numDecodings = 1.

Likewise for the empty string, the numDecodings = 1 as input string would have been "" as well.

This problem is recursive and can be broken in sub-problems. We start from start of the given digit sequence. We initialize the total count of decodings as 0. We recur for two subproblems.

  1. If the ith digit is non-zero, recurse for remaining (i+1) digits and add the result to total count.
  2. If the first two digits form a valid character (or smaller than 27), recur for remaining (i+2) digits and add the result to total count.

We can also start from the end of the string, following similar logic.

Code

Java

Recursion (left to right):

// Given a digit sequence of length n,
// returns count of possible decodings by
// replacing 1 with A, 2 woth B, ... 26 with Z
int numDecodings(String s){
	return helper(s.toCharArray(), 0);
}
static int helper(char[] digits, int idx) {
	if(idx >= digits.length){
		return 1;
	}
	char curr = digits[i];
	int ans = 0;
	if('1' <= curr && curr <= '9'){
		ans = dfs(digits, idx+1);
	}
	if(i+1 < digits.length){
		char next = s.charAt(i+1);
		if(('1' == curr) ||
           ('2' == curr && '0' <= next && next <= '6')) {
                ans += dfs(s, i+2, cache);
        }
	}

	return ans;
}

Complexity

  • ⏰ Time complexity: O(2^n)
  • 🧺 Space complexity: O(n)

Dry Run

Here we are going from left to right.

numWays("12345") = "A" + numWays("2345") and "L" + numWays("345")

In the above logic, we have not handled the case when data starts with 0. eg.

numWays("011") = 0

To do so, we can do following:

if(digits[idx] == ‘0'){
    return 0;
}

Now, handle when we get numWays as negative and return the value accordingly.

The time complexity of above the code is exponential. If we take a closer look at the above program, we can observe that the recursive solution is similar to Generate Nth Fibonacci Number.

Method 2 - Top Down DP with Memoization OR DFS with Cache

If we look a the recursive solution, we are solving same problem again and again. So, we can use memoization.

numDecodings ("") => 1 (empty string can be represented by empty string) (i.e. numDecodings[n] = 1)

NOTE: only for build up with a valid string. Empty string on it’s own doesn’t need to be decoded.

Code

Java
public int numDecodings(String s) {
	int[] cache = new int[s.length()];
	// use -1 as "not yet initialized"
	Arrays.fill(cache, -1);
	return dfs(s, 0, cache);
}

private int dfs(String s, int idx, int[] cache) {
	if(idx >= s.length()) {
		return 1;
	}
	// check if cache is set
	if(cache[idx] > -1) {
		return cache[idx];
	}
	char curr = s.charAt(idx);
	int ans = 0;
	// check if single digit grouping is valid
	if('1' <= curr && curr <= '9') {
		ans = dfs(s, idx+1, cache);
	}
	int resultDoubleDigit = 0;
	// check if double digit grouping is valid
	if(idx+1 < s.length()) {
		char next = s.charAt(idx+1);
		if(('1' == curr)
		  || ('2' == curr && '0' <= next && next <= '6')) {
			ans += dfs(s, idx+2, cache);
		}
	}
	cache[i] = ans;
	return ans;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n) As, we are now caching the value now, we don’t have to go into 2^n paths.

Method 3 - Bottom up DP

Code

Java
int numDecodings(String s) {
	int[] dp = new int[s.length() + 1];
	dp[0] = 1; // there is only 1 way to decode empty string
	        // if 0th value is 0, we cannot decode it
	if (s.charAt(0) != '0') {
		dp[1] = 1;
	} else {
		return 0;
	}
	for (int i = 2; i < s.length() + 1; i++) {
		int oneDigit = Integer.parseInt(s.substring(i - 1, i));
		int twoDigits = Integer.parseInt(s.substring(i - 2, i));

		if (twoDigits >= 10 && twoDigits <= 26) {
			dp[i] += dp[i - 2];
		}
		// oneDigit can be 0
		if (oneDigit >= 1) {
			dp[i] += dp[i - 1];
		}
		// twoDigits cannot be 01 etc
		if (twoDigits >= 10 && twoDigits <= 26) {
			dp[i] += dp[i - 2];
		}
	}
	return dp[s.length()];
}

We can also calculate oneDigit and twoDigits like this:

int x = (chars[i - 2] - '0')
int y = (chars[i - 1] - '0');

int oneDigit = y;
int twoDigits = x * 10 + y;