Decode Ways (Leetcode 91)

This is the solution for Leetcode problem number 91 Decode ways(https://leetcode.com/problems/decode-ways/)

I am gonna explain this in parts. Firstly we will start with a recursion solution as it is the most intuitive way of thinking while attempting a DP question. Then we are gonna come with the Dynamic Programming solution using Memoization.

Recursive Solution

The pattern we are gonna apply here can be further used to calculate the total number of possibilities or choices for any kind of problem. Similar problems are Fibonacci, Staircase etc.

The choices we have is either we are gonna pick the next character and decode it or we pick the next two characters and try to decode them. In case we encounter ‘0’ we are gonna return as we can not process this as the numbers start from 1. Another constraint is that while choosing the next two characters we should be able to parse them to valid 32 bit integers. Keeping these constraints in mind we can start writing out recursive solution.

public class Solution {
public int NumDecodings(string s)
{
if(string.IsNullOrEmpty(s)) return 0;
return Recurse(s,0);
}
private int Recurse(string s,int index)
{
if(index == s.Length)
{
return 1;
}
if(s[index] == '0')
{
return 0;
}
int firstWay = Recurse(s,index+1);
int secondWay = 0;
if(index+2 <= s.Length && Convert.ToInt32(s.Substring(index,2)) <= 26)
{
secondWay = Recurse(s,index+2);
}
return firstWay + secondWay;
}
}

Here first way and second way are the two choices we are making. While processing second way we have to take care of the index out of range exception and also that the substring so obtained can be parsed to 32 bit integer. In the end we add the two ways to get the total ways. The exit condition is when we reach the end of the string. We are checking for s.Length and not s.Length-1 as while taking two characters at a time we escape s.Length-1.

In the above image I have tried to draw the recursion tree to decode a string “11106”.

It decodes successfully in two ways as

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

Notice that the above recursion tree has many repetitive parts namely we are calculating the ways for (11106,2) twice, (11106,3) thrice and so on. This takes the time complexity to exponential terms. We will try to reuse our computed values in the DP solution.

DP using Memoization

Once we have the recursion solution we can optimize it by using the precomputed values. Notice once we have the values for (11106,2) we can use it for future needs and need to do the entire computation again.

We do so by creating an array of string size. As we can observe from the signature of our recursive method named “Recurse” the only thing changing is the index, so we map our ways to the index.

We store the number of ways calculated for every index and reuse the result where ever required. For every call we first check if we have calculated the ways already by checking if DP[index] != 0. If so we use return the calculated value as DP[index]. If not we calculate the ways and store it as DP[index] = first way + second way, and return DP[index];

public class Solution {
public int NumDecodings(string s)
{
if(string.IsNullOrEmpty(s)) return 0;
int[] dp = new int[s.Length];
return Recurse(s,0,dp);
}
private int Recurse(string s,int index,int[] dp)
{
if(index == s.Length)
{
return 1;
}
if(dp[index]!=0) return dp[index];
if(s[index] == '0')
{
return 0;
}
int firstWay = Recurse(s,index+1,dp);
int secondWay = 0;
if(index+2 <= s.Length && Convert.ToInt32(s.Substring(index,2)) <= 26)
{
secondWay = Recurse(s,index+2,dp);
}
dp[index] = firstWay + secondWay;
return dp[index];
}
}

This reduces the Time Complexity to O(N) and space complexity to O(N)(for DP array), not including the space for recursive stack.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store