Number of ways to decode a message

Companies:
  • Amazon Interview Questions
  • Bloomberg Interview Questions
  • Cisco Interview Questions
  • Facebook Interview Questions
  • Goldman Sachs Interview Questions
  • Google Interview Questions
  • Microsoft Interview Questions

Problem Statement

A message containing letters from A-Z is being encoded to numbers using the following mapping:

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

Given a non-empty string containing only digits, determine the total number of ways to decode it.

Sample Test Cases

Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Problem Solution

We will be using Dynamic Programming to solve this problem.

Let’s think of the sub problem. To decode a message of n characters, you need to know in how many ways you can decode message using n-1 characters and a message using n-2 characters.

Why are we going only two steps back ie n-1 and n-2 if we are calculating for n? Because the letter can be either represented by one character or a two characters.

So on each step keeping in mind the constraint that coding of letter is constrained between 1 and 26 we cascade through the array summing the values at n-1 and n-2.

Complexity Analysis

Time Complexity: O(n) as we are traversing through the entire array once.

Space Complexity: O(n) we have to maintain the dp array which has same size as string.

Code Implementation

#include<bits/stdc++.h>
using namespace std;

int numDecodings(string s) {
        vector<int>dp(s.size()+1,0);
        dp[0]=1;dp[1]=1;
        if(s[0]=='0')return 0;
        for(int i=2;i<=s.size();i++){
            if(s[i-1]>'0')dp[i]=dp[i-1];
            if(s[i-2]=='1'||(s[i-2]=='2'&&s[i-1]<'7'))dp[i]+=dp[i-2];
        }
        return dp[s.size()];
    }
int main()
{
    string s="226";
    int x= numDecodings(s);
    cout<<x;
}

 

public class Decode
{
    public int numDecodings(String s) 
    {
        if (s == null || s.length() == 0) 
            return 0;
        
        int n = s.length();
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = s.charAt(0) != '0' ? 1 : 0;
        
        for (int i = 2; i <= n; i++) 
        {
            int first = Integer.valueOf(s.substring(i - 1, i));
            int second = Integer.valueOf(s.substring(i - 2, i));
            
            if (first >= 1 && first <= 9) 
               dp[i] += dp[i-1];  
            
            if (second >= 10 && second <= 26) 
                dp[i] += dp[i-2];
            
        }
        return dp[n];
    }

    
    public static void main(String[] args) 
    {
        Decode d = new Decode();
        String s = "226";
        System.out.println(d.numDecodings(s));
        
    }
    
}

 

def numDecodings(s):
    if not s or s[0] == '0':
        return 0
        
    prev, curr = 1, 1 
    for i in range(1,len(s)):
      
        if s[i] == '0':
            curr = 0
       
        if s[i-1] == '1' or (s[i-1] == '2' and s[i] <= '6'):
            tmp = curr
            curr += prev  
            prev = tmp  

        else:
            prev = curr  
    return curr

print(numDecodings("226"))

 

Scroll to Top