DECODE STRING

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
1 upvote
Asked in company
Twilio

Problem statement

A message containing letters from A-Z can be encoded into numbers using the following mapping:

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

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways).

Given a string ‘S’ containing only digits, return the number of ways to decode it.

Example: 
Input: ‘S’ = "11106"

Output: 2


The possible ways are:-
(1 1 10 6),
(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".
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains ‘T’, denoting the number of test cases.    

Each test case's first and only line contains the string ‘S’.
Output format : 
Return the number of ways to decode the string ‘S’.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T  <= 10
1 <= | S | <= 100

Time Limit: 1 sec
Sample Input 1 :
2
12
226
Sample Output 1 :
2
3
Explanation Of Sample Input 1 :
For the first test case:-
"12" could be decoded as "AB" (1 2) or "L" (12).

For the second test case:-
"226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
Sample Input 2 :
2
1234
333
Sample Output 2 :
3
1
Hint

 Think of the possible choices you might make and try to solve them with the help of recursion.

Approaches (3)
Recursion

Function numDecodingsUtil( string S, int i, int N )

  1. First, write the base cases:
    • if i<’N’ && S[i]==’0’, return 0.
    • If i>= ’N’, return 1.
  2. Then, declare and initialize a variable ‘ways’ to 0.
    • Go for option 1. Call the numDecodingsUtil 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 numDecodingsUtil for index i+2 again and add the returned value to ‘ways’.
  3. At last, return ‘ways’.

Function numDecodings(string S):

  1. call numDecodingsUtil with index as 0 and length of ‘S’.
Time Complexity

O(2^N), where ‘N’ is the length of the string ‘S’.

 

 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).

 

Hence, the time complexity is O(2^N).

Space Complexity

O( N ), where ‘N’ is the length of the string ‘S’.

 

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).

 

Hence the space complexity is O( N ).

Code Solution
(100% EXP penalty)
DECODE STRING
Full screen
Console