DECODE STRING

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

The above approach took a lot of execution time because we call the function numDecodingsUtil 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 we already calculated. 

The new things we do here is just that we store the answers returned by numDecodingsUtil in an array ‘DP’, where DP[i] denotes the number of ways to decode string S[i, N], and every time there is the function call for numDecodingsUtil at index i, we check if we’ve already calculated the value of DP[i]. 

The Steps are as follows:

Function numDecodingsUtil( string S, int i, int N , [int] DP)

1. First, write the base cases:
   • if i<N && S[i]==’0’, return 0.
   • If i>=N, return 1.
2. 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.
3. 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, and call numDecodingsUtil for index i+2 again and add the returned value to ‘ways’.
4. At last, return ways and also update DP[i]=  ’ways’.

Function numDecodings(string S):

1. Initialize an array ‘DP’ of size ‘N’ with -1.
2. Return numDecodingsUtil(S, 0, length of ‘S’ ,DP).

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 ‘secondPrev’ respectively. 

The Steps are as follows:

Function numDecodings( string S ):

1. 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.
2. If not, then initialize three variables, namely, ‘prev’ to value 1, ‘secondPrev’=1 and ‘current’ to 0.
3. 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 the 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 ‘secondPrev’ to ‘current’.
   • Now, for the next i, update the value of ‘prev’ and ‘secondPrev’. secondPrev=prev and prev=current.
4. Return prev as this will contain the final answer.