91. Decode Ways

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

'A' -> "1"

'B' -> "2"

...

'Z' -> "3"

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

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

The answer is guaranteed to fit in a 32-bit integer.

Example: 1

Input: s = "12"

Output: 2

Example: 2

Input: "226"

Output: 3

Example: 3

Input: "0"

Output: 0

Constraints:

• 1 <= s.length <= 100
• s contains only digits and may contain leading zero(s).

Step I (Observation and marking valid and invalid states):

• First of all we know that the numbers range from 1 to 26. So any number having no of digits greater than two can be discarded.
• Also '0' cannot be taken as an element, because '0' has no mapping. It can only be considered if it is preceded by a '1' or '2'.
• So we will mark in our boolean array: For every index 'i' can we take 1 position (i.e [i, i]) and can we take two positions (i.e [i, i + 1]).
• If yes we will mark them true, otherwise false.
• This is done in the code below.

Marking valid and invalid states: gr = new boolean[s.length()][s.length()]; for(int i = 0; i < s.length(); i++) { // if the current pos starts with '0' // it must be ignored if(s.charAt(i) == '0') { continue; } int num = 0; for(int j = i; j < s.length(); j++) { // checking if the number lies in [1, 26] num = num * 10 + (s.charAt(j) - '0'); if(num >= 1 && num <= 26) { gr[i][j] = true; } else { break; } } }

Step II (Solving the problem using Recursion):

• Now we will compute the result by considering [l, r] ranges.
• If range [l, r] is valid, then we will compute result for ranges [l + 1, l + 1] and [l + 1, l + 2]. If it is invalid we can simply return 0, because this combination won't give us any answer.
• Also if current range [l, r] is valid and 'r' equals the last index of string, then we can return 1.
• One more condition to check is that, if 'r' exceeds the last index of string, since there isn't any character for combination, we can say that such string cannot exist. So we will return 0.
• This step is shown in code below.

Solving using recursion (Will give TLE): int noOfWays(int l, int r) { if(r >= gr.length) return 0; // checking if current state is valid // if invalid, return 0 if(!gr[l][r]) return 0; // checking for valid cases if(gr[l][r]) { if(r == gr.length - 1) { // reached end of string // found a valid combination return 1; } else { // haven't reached the end of string // will go to next states return noOfWays(r + 1, r + 1) + noOfWays(r + 1, r + 2); } } return 0; }

Step III (Using DP: From TLE to Accepted):

• Now for every state [l, r] we might be recomputing them again and again during recursion.
• This can result into TLE.
• So what we will do is, after computing value of [l, r] we will store it into dp array mapping them by [l, r].
• This step is shown in code below.

Full Code (Java): class Solution { boolean[][] gr; int[][] dp; public int numDecodings(String s) { gr = new boolean[s.length()][s.length()]; for(int i = 0; i < s.length(); i++) { if(s.charAt(i) == '0') { continue; } int num = 0; for(int j = i; j < s.length(); j++) { num = num * 10 + (s.charAt(j) - '0'); if(num >= 1 && num <= 26) { gr[i][j] = true; } else { break; } } } dp = new int[gr.length][gr.length]; for(int i = 0; i < dp.length; i++) Arrays.fill(dp[i], -1); return noOfWays(0, 0) + noOfWays(0, 1); } int noOfWays(int l, int r) { if(r >= gr.length) return 0; if(!gr[l][r]) return 0; // checking if we have stored value of current subproblem // if yes, return its value if(dp[l][r] != -1) { return dp[l][r]; } if(gr[l][r]) { if(r == gr.length - 1) { return 1; } else { // storing the value of subproblem [l, r] in dp[][] dp[l][r] = noOfWays(r + 1, r + 1) + noOfWays(r + 1, r + 2); return dp[l][r]; } } return 0; } }

Note : You can reduce dp[N][N] and gr[N][N] to dp[N][2] and gr[N][2] since we only consider number with utmost 2 digits. This is left as an exercise to the reader.