Decode Ways

Difficulty Level Medium
Frequently asked in Adobe Amazon Cisco Databricks Facebook Goldman Sachs Google JP Morgan Microsoft Morgan Stanley Oracle Square
Dynamic Programming StringViews 2225

In Decode Ways problem we have given a non-empty string containing only digits, determine the total number of ways to decode it using the following mapping:

'A' -> 1

'B' -> 2

...

'Z' -> 26

Example

S = “123”

Number of ways to decode this string is 3

Decode Ways

If we look closely at the problem then we can observe that all the one-digit number except 0 are valid but in case of two-digit number only numbers from 10 to 26 are valid.

Hence we can conclude that at every index we have two steps:

1. If the ith element of a string is not ‘0’ then we have one way to decode the string starting with ith index using the mapping:

'A' -> 1

'B' -> 2

….

'I' -> 9

2. If we can merge the ith and (i+1)th index together to form a valid number using the following mapping:

'J' -> 10

'K' -> 11

….

'Z' -> 26

Then we have one more way to decode the string starting with ith index.

Algorithm for Decode Ways

Step 1: Declare and initialize a 1D array of size n with zero.

Step 2: Check if we can decode the string which starts and ends both at (n-1)th index( Base case ).

Step 3: Run a loop and check at every step if we can use the ith index element as one digit valid number or merge it with (i+1)th index element to form a valid number of two digit.

  1. If s[i]!=’0’, then dp[i]+=dp[i+1]
  2. If s[i]==’1’, then dp[i]+=dp[i+2]
  3. If s[i]==’2’ and s[i+1]<=’6’, then dp[i]+=dp[i+2]

Step 4: Return dp[0].

Implementation

C++ program for Decode Ways

#include<bits/stdc++.h>
using namespace std;
int numDecodings(string s) {
    int n=s.length();
    int dp[n+1];
    memset(dp,0,sizeof(dp));
    dp[n]=1;
    if(s[n-1]!='0'){       //if the last chararcter is not zero then we have one way to decode it
        dp[n-1]=1;
    }
    for(int i=n-2;i>=0;i--){
        if(s[i]!='0'){    
            dp[i]+=dp[i+1];
        }
        if(s[i]=='1'){
            dp[i]+=dp[i+2];
        }
        if(s[i]=='2'){
            if(s[i+1]<='6'){
                dp[i]+=dp[i+2];
            }
        }
    }
    return dp[0];
}
int main(){
    string s="452625";
    cout<<"The number of ways to decode the given string is: "<<numDecodings(s);
}
The number of ways to decode the given string is: 4

JAVA program for Decode Ways

public class Main
{
    public static int numDecodings(String s) {
        int n=s.length();
        int[] dp=new int[n+1];
        dp[n]=1;
        if(s.charAt(n-1)!='0'){       //if the last chararcter is not zero then we have one way to decode it
            dp[n-1]=1;
        }
        for(int i=n-2;i>=0;i--){
            dp[i]=0;
            if(s.charAt(i)!='0'){    
                dp[i]+=dp[i+1];
            }
            if(s.charAt(i)=='1'){
                dp[i]+=dp[i+2];
            }
            if(s.charAt(i)=='2'){
                if(s.charAt(i+1)<='6'){
                    dp[i]+=dp[i+2];
                }
            }
        }
        return dp[0];
    }
  public static void main(String[] args) {
      String s="23572";
    System.out.println("The number of ways to decode the given string is: "+numDecodings(s));
  }
}
The number of ways to decode the given string is: 2

Complexity Analysis for Decode Ways

Time complexity: O(n) where n is the length of the given string.

We are traversing the given string only once hence the complexity is O(n)

Space complexity: O(n) because we store the number of ways at each step in dp array which leads us to linear space complexity.

References

Translate »