Decode Ways Editorial

Practice Problem Link: Decode Ways

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

A message containing letters from 'A' to 'Z' is being encoded into numbers using the following encoding:

'A' -> 1
'B' -> 2
.
.
.
'Y' -> 25
'Z' -> 26

Given an encoded string, find the number of ways it can be decoded.

Naive Approach

A simple solution is to recursively try every possible combination of single-digit numbers and two-digit numbers less than 27 and keep the count of valid combinations.

Analysis

• Time Complexity: Exponential
• Auxiliary Space Complexity: O(1)

Implementation

C++

int mod = 1000000007;
int countWays(string str, int start, int end) {
	if(start > end || (start == end && str[start] != '0')) {
		return 1;
	} 
	if (str[start] == '0') {
		return 0;
	}
	int ways = 0;
	ways = (ways + countWays(str, start + 1, end)) % mod;
	if (start < end && (str[start] == '1' || str[start] <= '2' && str[start + 1] <= '6') ){
		ways = (ways + countWays(str, start + 2, end)) % mod;
	} 
	return ways;
}
int numDecodings(string str) {
	int start = 0;
    return countWays(str, start, str.size() - 1);
}

Java

class Solution {
	int mod = 1000000007;
	int countWays(String str, int start, int end) {
		if(start > end || (start == end && str.charAt(start) != '0')) {
			return 1;
		} 
		if (str.charAt(start) == '0') {
			return 0;
		}
		int ways = 0;
		ways = (ways + countWays(str, start + 1, end)) % mod;
		if (start < end && (str.charAt(start) == '1' || str.charAt(start) <= '2' && str.charAt(start + 1) <= '6') ){
			ways = (ways + countWays(str, start + 2, end)) % mod;
		} 
		return ways;
	}
	int numDecodings(String str) {
	    int start = 0;
  	    return countWays(str, start, str.length() - 1);
	}
}

Optimal Approach (Memoization)

The idea is similar to the naive solution but to avoid multiple computations for each index, we can memoize the subproblems so that the result of overlapping intervals can be computed in constant time.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(n)

Implementation

C++

int mod = 1000000007;
unordered_map<int, int> memoize;
int countWays(string str, int start, int end) {
	if(start > end || (start == end && str[start] != '0')) {
		return 1;
	} 
	if (str[start] == '0') {
		return 0;
	}
	if(memoize.find(start) != memoize.end()) {
		return memoize[start];
	}
	int ways = 0;
	ways = (ways + countWays(str, start + 1, end)) % mod;
	if (start < end && (str[start] == '1' || str[start] <= '2' && str[start + 1] <= '6') ){
		ways = (ways + countWays(str, start + 2, end)) % mod;
	} 
	memoize[start] = ways;
	return ways;
}
int numDecodings(string str) {
	memoize.clear();
    return countWays(str, 0, str.size() - 1);
}

Java

class Solution {
	int mod = 1000000007;
	HashMap<Integer, Integer> memoize = new HashMap<Integer, Integer>();
	int countWays(String str, int start, int end) {
		if(start > end || (start == end && str.charAt(start) != '0')) {
			return 1;
		} 
		if (str.charAt(start) == '0') {
			return 0;
		}
		if(memoize.containsKey(start)) {
			return memoize.get(start);
		}
		int ways = 0;
		ways = (ways + countWays(str, start + 1, end)) % mod;
		if (start < end && (str.charAt(start) == '1' || str.charAt(start) <= '2' && str.charAt(start + 1) <= '6') ){
			ways = (ways + countWays(str, start + 2, end)) % mod;
		} 
		memoize.put(start, ways);
		return ways;
	}
	int numDecodings(String str) {
	    memoize.clear();
    	return countWays(str, 0, str.length() - 1);
	}
}

Optimal Approach (Bottom-Up)

The optimal approach is based on dynamic programming. For every index i, the number of valid combinations up to ith index depends upon the number of valid combinations up to (i - 2)th index and (i - 1)th index.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(n)

Implementation

C++

int mod = 1000000007;
int numDecodings(string str) {
	if (str[0] == '0') {
		return 0;
	}
    int n = str.size();
	int currWays[n + 1] = {0};
	currWays[0] = 1;
	currWays[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (str[i - 1] > '0') {
			currWays[i] = currWays[i - 1];
		}
		if (str[i - 2] == '1' || (str[i - 2] == '2' && str[i - 1] <= '6')) {
			currWays[i] = (currWays[i] + currWays[i - 2]) % mod;
		}
	}
	return currWays[n];
}

Java

class Solution {
	int mod = 1000000007;
	int numDecodings(String str) {
	    if (str.charAt(0) == '0') {
			return 0;
		}
		int n = str.length();
		int[] currWays = new int[n + 1];
		currWays[0] = 1;
		currWays[1] = 1;
		for (int i = 2; i <= n; i++) {
			if (str.charAt(i - 1) > '0') {
				currWays[i] = currWays[i - 1];
			}
			if (str.charAt(i - 2) == '1' || (str.charAt(i - 2) == '2' && str.charAt(i - 1) <= '6')) {
				currWays[i] = (currWays[i] + currWays[i - 2]) % mod;
			}
		}
		return currWays[n];
	}
}