Last Updated: 13 Jan, 2021
Decode Ways
Moderate
Asked in companies
Given a string ‘strNum’ which represents a number, your task is to find the ways to decode the given string ‘strNum’.
The format of encoding is as follows: ‘A’ - 1, ‘B’ - 2, ‘C’ - 3, ‘D’ - 4, ……………, ‘Z’ - 26.
Encoding is possible in letters from ‘A’ to ‘Z’. There is an encoding between character and number.
Example :
‘n = 226’ so we can decode ‘226’ in such a way-
‘BZ = 2-26’, as B maps to 2 and Z maps to 26.
‘BBF = 2-2-6’
‘VF = 22-6’
‘226; can be decoded in three ‘BZ’, ‘BBF’, ‘VF’ possible ways.
Point to be noticed we can’t decode ‘226’ as ‘226’ because we have no character which can directly map with ‘226’ we can only decode numbers from ‘1’ to ‘26’ only.
Input format :
The first line of input contains an integer ‘T’ denoting the number of test cases. The 'T' test cases follow.
The first line of each test case contains a single string ‘strNum’.
Output Format :
For each test case, print an integer denoting the ways of decodes.
Note :
1. You do not need to print anything, it has already been taken care of. Just implement the given function.
2. Ways of decodes can be very high, so return answer modulo 10^9+7.
Constraints :
1 <= T <= 50
1 <= N <= 10^4
Time limit: 1 second
Approaches
The basic idea is that, try to use each and every possible combination.
- Use a function ‘decodeWaysHelper(strNum,n)’, where ‘strNum’ is a given number as a string, ‘n’ is the size of ‘strNum’. And ‘decodeWaysHelper’ returns the number of decode ways.
- If ‘n==0’ or ‘n==1’, then return ‘1’, because a single number can form only one character/ one way.
- If ‘strNum[n-1]’ is ‘0’ then return ‘0’ because we don't have a mapping of ‘0’ with any character.
- Else use a variable ‘count=0’ to store answer for first ‘n’ number of ‘strNum’
- called ‘decodeWaysHelper(strNum,n-1)’, stored the result in the ‘count’ variable, because the last digit can be from ‘1’ to ‘9’.
- If ‘strNum[n-2]==1’ then call ‘decodeWaysHelper(strNum,n-2)’ because last two digits can be from ‘11’ to ‘19’
- If ‘strNum[n-2]==2 and strNum[n-1]<7’ then call ‘decodeWaysHelper(strNum,n-2)’ because the last two digits can be from ‘20’ to ‘26’.
- At the end return count.
The basic idea is that, if the given number is 'xyz19' then the possible answer can be the answer of('xyz') use '19' as another character(‘s’) and answer of ( 'xyz1' ) use '9' as another character(‘i’).
- Make a 'dp' array, initially all the values of 'dp' is '0' and size of 'dp' is equal to size of given 'n' string.
- 'dp[0] =1 and dp[1]=1', because a single can make only one character.
- Iterate a loop from '2' to 'n-1'.
- If 'n[i-1]+n[i-2]' form a number from '10 to 26', then 'dp[i]=dp[i]+dp[i-2]', because we can make a new character with last two digit so answer will be- answer without last two digit('dp[i-2]').
- If('n[i]' not '0'), then add 'dp[i]=dp[i]+dp[i-1]', answer without the last single digit.
- At the end, return the last value in 'dp' / 'dp[(length of 'n') -1]'.
Similar problems