Decode Ways

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

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