Do you think IIT Guwahati certified course can help you in your career?
Introduction
In computer science, encoding and decoding are quite general terms. Encoding refers to changing some information into a form the computer can handle. For security purposes, encoding is done so that the encoded form should not be easy for the human brain to guess. Decoding is the reverse of encoding. It refers to 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 “Coding Ninjas Studio” before moving on to the solution approach.
Approach 1:Recursion
The idea is fairly simple. For every index, we’ve got 2 choices.
Pick only the current element as a single value between [1-9]
Pick 2 elements, i.e, current and the next, 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> usingnamespacestd;
intrec(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 return0; if(i >= n) //if out of the string, decoding is done in one way thus return 1. return1; 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; } intnumDecodings(string s) { int n = s.size(); //size of the string return rec(s, 0, n); //call and return rec function }
intmain() { string s; cin>>s; //input the string int ans = numDecodings(s); cout<<ans<<endl; return0; }
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).
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 initialize 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, 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> usingnamespacestd;
intrec(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 return0; if(i >= n) //if out of the string, decoding is done in one way thus return 1. return1; 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] } intnumDecodings(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 }
intmain() { string s; cin>>s; //input the string int ans = numDecodings(s); cout<<ans<<endl; return0; }
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. 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 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> usingnamespacestd; intnumDecodings(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 return0; //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; }
intmain() { string s; cin>>s; //input the string int ans = numDecodings(s); cout<<ans<<endl; return0; }
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: The only space taken here is by the variables that take constant space. So space complexity will be constant.
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.
What are overlapping subproblems?
A problem has overlapping subproblems if it can be divided into smaller problems that are reused multiple times.
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.
What is encoding?
Encoding refers to changing some information into a form that the computer can handle.
What is decoding?
Decoding refers to the process of finding the original information using the encoded information.
To practice more such problems, Code360 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.
130+ registered 
