Decode ways

Shreya Deep
Last Updated: May 13, 2022

Introduction

In computer science, encoding and decoding are quite general terms. Encoding refers to changing some information into a form that the computer can deal with. For security purposes, encoding is done so that the encoded form should not be easy to guess by the human brain. Decoding is the reverse of encoding. It refers to the process of finding the original information using the encoded information. 

In this article, we’ll learn how many ways we can decode a given string given the rules with which it was encoded earlier. 

Problem Statement

You are given a string s, containing only digits. Return the number of ways to decode it. 

The original string (which contained only alphabets) was encoded using the following rules:

The letters A-Z can be encoded into numbers. The mapping is:

‘A’ -> ‘1’, ‘B’ -> ‘2’, ‘C’->’3’, ….., ‘Z’->’26’. 

Now, to decode the digit string, you must be convinced that at any position i, we can look for a maximum of two characters for decoding, one, the character at ith position (which must be between ‘1’ to ‘9’), and the other, (character at ith position + character at (i+1)the position), only if it is between ‘10’ to ‘26’. 

For example:

 “11106” can be mapped into:

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

Examples: 

INPUT : s = “12”

OUTPUT:  2

"12" could be decoded as "AB" (1 2) or "L" (12).

INPUT : s = “226”

OUTPUT:  3

"226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Recommended: Please try it on “CodeStudio” before moving on to the solution approach.

Approach 1:Recursion

The idea is fairly simple. For every index, we’ve got 2 choices. 

  1. Pick only the current element as a single value between [1-9]
  2. Pick 2 elements i.e current as well as the next element to make a couple. This value will be [10, 26]. 

Thus we solve the problem recursively (where the function returns the number of ways to decode)  with the above 2 choices and whenever we reach the end i.e index >= n simply return 1. This means that we have got one way to decode the string. 

So, for the ith index:

  • Option1 (single pick): pick s[i] and call for i+1. Note that In the case of a single pick, the element should not be '0' as it is invalid. Thus, ways = decode(s,i+1,n)
  • Option2 (double pick): pick s[i+1] also along with s[i], if ‘10’<s[i]+s[i+1]<’26’. You need to specifically check that it lies in that range. Also, ensure that i+1<n, otherwise it’ll be out of range. 

Base cases:

  • If the current character is 0, we just need to return 0 as there can’t be any decoding corresponding to 0 or starting with 0.
  • If the i>=n, that means we’ve already reached the end of the string and the whole string has been decoded so just return 1. 

Steps are:

  • Input the encoded string s and call the function numDecodings, passing s as a parameter.
  • In the numDecodings function, call another function “rec” which will have 3 parameters, string s, integer i (which is the index we’re currently working on) and integer n (which will be the length of the encoded string). While calling the “rec” function, we pass the values (s,0,n) because initially, we’ll be working on index 0.
  • In the rec function:
    • First write the base cases:
      •  if i<n && s[i]==’0’, return 0.
      • If i>=n, return 1.
    • Then, declare and initialize a variable “ways” to 0.
      • Go for option 1. Call the “rec” function for index i+1 again and add the returned value to “ways”.
      • For option 2, check if we can take (i+1)th character. For that check if ((i+1)<n && ((s[i] == '1' && s[i] <= '9') || (s[i]=='2' && s[i+1] < '7'))), i.e., if it lies inside the string and also in the range [“10”,”26”]. If yes, go for option 2, and call “rec” for index i+2 again and add the returned value to “ways”.
    • At last, return ways. That will be the final answer.
  • Print the answer.

C++ implementation

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

int rec(string& s, int i, int n){
    if(i < n && s[i] == '0'//If the character at i is 0, there can't be any answer
        return 0;
    if(i >= n) //if out of the string, decoding is done in one way thus return 1.
        return 1;
        
    int ways = 0// this will store the answer for current i.
    // option1 
    if(s[i] != '0') ways = rec(s, i+1, n);
    // option 2
    if(i+1 < n && ((s[i] == '1' && s[i+1] <= '9') || (s[i]=='2' && s[i+1] < '7')))
        ways += rec(s, i+2, n);
          
    return ways;
}
    
int numDecodings(string s) {
    int n = s.size(); //size of the string
    return rec(s, 0, n); //call and return rec function
}

int main()
{
    string s;
    cin>>s; //input the string
    int ans = numDecodings(s);
    cout<<ans<<endl;
    return 0;
}

 

Input

226

 

Output

3

Complexities

Time complexity

O(2^n), where n is the length of the string.

Reason: In the worst case, for each index i, we can maximum make 2 recursion calls for each i. Thus the complexity will be exponential and equal to O(2^n).

Space complexity

O(n), where n is the length of the string.

Reason: In the worst case, the extra space used by the recursion stack can go up to a  maximum depth of n. Hence the space complexity is O(n).

Approach 2: Dynamic Programming

The above approach took a lot of execution time because we call the function “rec” for one substring more than once. So we can optimize it and the best way to optimize it will be using dynamic programming to remember the answers for substrings that we already calculated. 

The new things we do here, is just that we store the answers return by rec in a vector dp, where dp[i] denotes the number of ways to decode string s[i,n], and every time there is the function call for rec at index i, we check if we’ve already calculated the value of dp[i]. 

Steps are:

  • Input the encoded string s and call the function numDecodings, passing s as a parameter.
  • In the numDecodings function, declare the vector dp of size n and initialise all the values to -1. Call another function “rec” which will have 4 parameters, string s, integer i (which is the index we’re currently working on), integer n (which will be the length of the encoded string) and the vector dp. While calling the “rec” function, we pass the values (s,0,n,dp) because initially, we’ll be working on index 0. Return the value returned by “rec”.
  • In the rec function:
    • First write the base cases:
      •  if i<n && s[i]==’0’, return 0.
      • If i>=n, return 1.
    • If it’s not the base case, check if the answer is already calculated, i.e., if dp[i]!=-1. If yes, return the value already. If not, move forward to the next steps.
    • Then, declare and initialize a variable “ways” to 0.
      • Go for option 1. Call the “rec” function for index i+1 again and add the returned value to “ways”.
      • For option 2, check if we can take (i+1)th character. For that check if ((i+1)<n && ((s[i] == '1' && s[i] <= '9') || (s[i]=='2' && s[i+1] < '7'))), i.e., if it lies inside the string and also in the range [“10”,”26”]. If yes, go for option 2, and call “rec” for index i+2 again and add the returned value to “ways”.
    • At last, return ways and also update dp[i]=ways. That will be the final answer.
  • Print the answer returned by the function numDecodings.

C++ implementation

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

int rec(string& s, int i, int n,vector<int>&dp){
    if(i < n && s[i] == '0'//If the character at i is 0, there can't be any answer
        return 0;
    if(i >= n) //if out of the string, decoding is done in one way thus return 1.
        return 1;
    if(dp[i]!=-1){//Check if the answer for this i is already calculated.
        return dp[i];
    }
    int ways = 0// this will store the answer for current i.
    // option1 
    if(s[i] != '0') ways = rec(s, i+1, n,dp);
    // option 2
    if(i+1 < n && ((s[i] == '1' && s[i+1] <= '9') || (s[i]=='2' && s[i+1] < '7')))
        ways += rec(s, i+2, n,dp);
          
    return dp[i]=ways; //Return and store the answer in dp[i]
}
    
int numDecodings(string s) {
    int n = s.size(); //size of the string
    vector<int>dp(n,-1);
    return rec(s, 0, n,dp); //call and return rec function
}

int main()
{
    string s;
    cin>>s; //input the string
    int ans = numDecodings(s);
    cout<<ans<<endl;
    return 0;
}

 

Input

226

 

Output

3

Complexities

Time complexity

O(n), where n is the length of the string.

Reason: Apparently, we’re only calculating the answer for each index from i=0 to n-1 once only. Thus the complexity will be linear and equal to O(n).

Space complexity

O(n), where n is the length of the string.

Reason: Only space taken here is by the dp vector of size equal to the length of the string. Thus space complexity is O(n).

Approach 3: Constant space solution

You can clearly see here that the answer for an ith index is either the sum of the answer for (i-1)th index and (i-2)th index (in the case we’re able to use option2) or just equal to the answer of (i-1)th index (in the case we’re only going for option1). So we’re going to use this fact and just store the values for (i-1)th index and (i-2)th index into two variables “prev” and “second_prev” respectively. 

Steps are:

  • Input the encoded string s and call the function numDecodings, passing s as a parameter.
  • In the numDecodings function, 
    • first, check if the length of the string is 0 or the first character itself is 0? If yes, then return 0 as there can’t be an answer in these situations.
    • If not, then initialise three variables, namely, “prev” to value 1, “second_prev”=1 and current to 0.
    • Then, run a loop from i=0 to i<s.length(), and for each i, 
      • Check if s[i]==0, if yes, then current will be 0.
      • If not, then we can go for option1 and take a single-digit number for decoding. Thus current=current+prev.
      • Now for whether to go for option 2 or not, check if the combination of s[i-1] and s[i] lies in the range [10,26]. If yes, we can take and thus add second_prev to current.
      • Now, for the next i, update the value of prev and second_prev. second_prev=prev and prev=current.
    • Return prev as this will contain the final answer. 

C++ implementation

#include<bits/stdc++.h>
using namespace std;
    
int numDecodings(string s) {
        if(s.length()==0 || s[0]=='0'//check if the length of the string is 0 or the first character itself is 0
            return 0;
        //Declare and initialize the three variables
        int second_prev=1;
        int prev=1;
        int current=0;
        for(int i=0;i<s.length();i++)
        {
            current=0;
            if(s[i]=='0'//If the current character, we can't go for option 1.
                current=0;
            else //Otherwise, we can and thus add prev to current.
                current+=prev;
            if(i>=1 && (s[i-1]=='1' || (s[i-1]=='2' && s[i]<='6'))) // If s[i-1]+s[i] is in the 
                //range [10,26], we can go for option 2.
                current+=second_prev;
            //Update for the next i.
            second_prev=prev;
            prev=current;
        }
        //Return prev
        return prev;
    }

int main()
{
    string s;
    cin>>s; //input the string
    int ans = numDecodings(s);
    cout<<ans<<endl;
    return 0;
}

 

Input

226

 

Output

3

Complexities

Time complexity

O(n), where n is the length of the string.

Reason: We’re traversing the string once and that takes O(n) time.

Space complexity

O(1)

Reason: Only space taken here is by the variables which take constant space. So space complexity will be constant.

Frequently asked questions

  1. What is dynamic programming, and where is it used?
    Dynamic programming is an optimization method used in various programming problems. It is used in problems where the solution depends on smaller overlapping subproblems. We use it to memorize the results so that they can easily be used later when needed.
  2. What are overlapping subproblems?
    A problem has overlapping subproblems if it can be divided into smaller problems that are reused multiple times.
  3. What is an optimal substructure?
    A problem is said to have an optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems.
  4. What is encoding?
    Encoding refers to changing some information into a form that the computer can deal with.
  5. What is decoding?
    Decoding refers to the process of finding the original information using the encoded information.
  6. Are there more Data Structures and Algorithms problems in CodeStudio?
    Yes, CodeStudio is a platform that provides both practice coding questions and commonly asked interview questions. The more we’ll practice, the better our chances are of getting into a dream company of ours.

Key Takeaways

In this article, we discussed the problem - Decode ways. Similar problems are: Decode stringencode and decode, and Decoded string. One of the efficient solutions to this problem was based on the concept of dynamic programming. This is one of the very interesting and crucial topics and problems based on this are asked during various coding contests as well as placements tests. I suggest you solve more problems based on this. Some of these are Maximum profitLongest Common prefixwildcard pattern matching, and rod cutting problem.


To practice more such problems, Codestudio is a one-stop destination. You can also Attempt our Online Mock Test Series. This platform will help you acquire effective coding techniques and give you an overview of student interview experience in various product-based companies.

Happy Coding!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think