Table of contents
Hello, reader 👋🏽 ! Welcome to the first post of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.
Disclaimer ⚠️ : These posts could involve considerable amount of rambling since I will definitely be sharing my thought process as well.
Today, I will be picking up LeetCode's daily challenge problem. Decode Ways.
🤔 Problem Statement
A message containing letters could be encoded into numbers as follows:
"A" -> 1
"B" -> 2
...
"Y" -> 25
"Z" -> 26
**Given an encoded message consisting of numbers, return the number of ways these numbers could be grouped and decoded.
- For e.g.:
226can be decoded into 2 ("B"), 22 ("U"), and 26 ("Z"). - Another e.g.:
06cannot be decoded because there's no mapping for 0 to any letter, and 06 is different from 6 (decoded to "F").
📌 Read the entire problem here.
💬 Thought process
This problem was a surprise since I'd solved this just a week before! So, I will mention here the thoughts I had for this problem when I first it question last week.
- When I skimmed through the problem, I saw the word "group" and the first thought I had was subsequences. The example clearly showed that we can only group numbers that appear simultaneously.
- On reading the statement further, I saw
number of ways. This gave a clue that I can generate all the groups and then return the total ways. Thus Recursion occurred to me! Then I started figuring out the pattern to group letters to come up with a recurrence and sub-problems. Upon further scrutiny, I came up with the following conclusions:
- I can either pick a number alone at index i, or I can pick up 2 characters i and i+1 together to decode the string. Why? Because the mapping between alphabets -> numbers are of the range [1, 26].
- If at any such substring, the first encoded character is 0, then I cannot further break it down.
- When I group 2 characters, i and i+1, I need to ensure that the 2 numbers are within range [10,26]. Say if I encounter 34, then I cannot break this string down further.
With these observations, I tried to draw a rough recursive tree.
- As you can see from the image above, there are 3 ways to group the message
226. - Now, I tried to draw for another string particularly one that involved a wrong grouping.
- In the above image for message
325, notice how when you break 3 and 32, but 32 cannot be broken further.
Let's look at the base cases now.
- If the string to process is empty, then you've found 1 way to decode
if the first character is '0' then you return 0, because you cannot break down the remaining string.
Also note: before making a recursive call, we need to check if it's even possible to make the next call.
- For example, let's assume the string "226", the calls would be as follows:
- Notice how, when you make a call from F("6"), you cannot consider selecting 2 characters, because there's not enough string left.
- If you carefully observer, you can choose 2 characters and then make a call further only of:
- There are enough characters left in the string to make a call
length > 1 - The chosen characters are of the form:
- "1x", where x can be any number from 0 to 9
- "2x", where x can be numbers only between [1,6] (because mappings only exist from 20 to 26)
- There are enough characters left in the string to make a call
Now that these are stated, let's look at the code
class Solution {
public int numDecodings(String s) {
if(s == null || s.length() == 0) {
return 0;
}
return decode(s);
}
private int decode(String s) {
int n = s.length();
// You've found 1 way to decode
if(n == 0) {
return 1;
}
char firstChar = s.charAt(0);
// If the first character is 0, you cannot break down the string further
if(firstChar == '0') {
return 0;
}
// Choose only 1 character or choose 2 characters
int chooseOneChar = decode(s.substring(1));
int chooseTwoChar = 0;
if(isValidString(s, 2, n)) {
// validate if you can select 2 characters
chooseTwoChar = decode(s.substring(2));
}
return chooseOneChar + chooseTwoChar;
}
private boolean isValidString(String s, int numChars, int n) {
// Only if n > 1, you can choose 2 characters
if(n > 1) {
String firstTwoChars = s.substring(0,2);
char firstChar = firstTwoChars.charAt(0);
char secondChar = firstTwoChars.charAt(1);
// If the string is of the form "1x" or "2x", then you this is a valid group
if(firstChar == '1' || firstChar == '2' && secondChar < '7') {
return true;
}
}
return false;
}
}
- The above code is contains everything I stated above.
Time Complexity: O(2^n), n = length of string (depth of the recursion tree). In the worst case you consider every individual character as separate groups Space Complexity: O(n), n = length of string => implicit stack space As you can see the TC is terrible, If you submit this code, it will result in TLE. Hence, we will have to optimise.
If you've observed carefully, there are overlapping subproblems. Let me show you an example.
- This is only a small example. Think of a string with 100 characters (LeetCode constraints, 100 is the max length of the i/p string). You'll get a lot of overlapping problems in a huge string.
- So, we can use DP to improve the algorithm and I'll use memoization. But before that, let's think of the problem in indices.
- Look at the image below.
- At every index i, you make a call to F(i+1) [choose only ith character] or (and) F(i+2) [choose ith and i+1th characters]
Let's look at the code for this now.
class Solution {
public int numDecodings(String s) {
if(s == null || s.length() == 0) {
return 0;
}
int n = s.length();
int[] memoized = new int[n];
// We fill the memoized indices with -1, so that we can differentiate
// between solved and unsolved sub-problems
Arrays.fill(memoized, -1);
return decodeMemoized(s, 0, memoized);
}
private int decodeMemoized(String s, int index, int[] memoized) {
int n = s.length();
// You've found 1 way to decode
if(index == n) {
return 1;
}
// If the sub-problem was already solved, return memoized answer
if(memoized[index] != -1) {
return memoized[index];
}
char firstChar = s.charAt(index);
// If the character at index is 0, you cannot break down the string further
if(firstChar == '0') {
memoized[index] = 0;
return 0;
}
// Choose only 1 character or choose 2 characters
int chooseOneChar = decodeMemoized(s, index+1, memoized);
int chooseTwoChar = 0;
if(isValidString(s, index, 2, n)) {
// validate if you can select 2 characters
chooseTwoChar = decodeMemoized(s, index+2, memoized);
}
memoized[index] = chooseOneChar + chooseTwoChar;
return memoized[index];
}
private boolean isValidString(String s, int index, int numChars, int n) {
// Only if index < n-1, you can choose 2 characters
if(index < n-1) {
String firstTwoChars = s.substring(index, index+2);
char firstChar = firstTwoChars.charAt(0);
char secondChar = firstTwoChars.charAt(1);
// If the string is of the form "1x" or "2x", then you this is a valid group
if(firstChar == '1' || firstChar == '2' && secondChar < '7') {
return true;
}
}
return false;
}
}
- I've changed the signature of the function now, and I'm passing the index we are processing as well as the memoized results.
- Every time we want to solve a sub-problem at index i, we check if it was solved before. If yes, then we return the memoized result.
- If not, we compute the result, memoize and then return the result to the caller.
Time Complexity: O(n), n = length of string. In the worst case, the recursion tree would have a depth of n.
Space Complexity: O(n), n = length of string => implicit stack space (also we are using aux space for memoizing the results)
- Note: This solution can further be optimised to:
- Avoid stack space to only use O(n) space for memoizing results => tabulation
- And O(1) space to avoid memoizing all n values and use constant space to save the last 2 results.
Although I will not be discussing the two approaches, you can find them here.
Conclusion
That's a wrap for todays problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!
Thank you for reading!