Congratulations to you on completing Level-1 successfully. We hope that your journey was smooth and you learnt a lot from it.
Don't stop now!
Since you have learned the basics of Data Structures and Algorithms, it is the best time to practice a lot of advanced problems on the topics that were covered in Level-1. How?
Well, Level-2 has been prepared to serve the purpose.
Now we will start with Level-2. First module of level-2 is "Conceptual Building Blocks" and we will start with its first sub module, "Recursion and Backtracking."
Moving further, in this article we will discuss about the first problem based on "Recursion and Backtracking" i.e. Abbreviation using Backtracking.
Understanding the problem:
You are given a word.
You have to generate all abbreviations of that word.
For example:
Sample Input-> pep
Sample Output-> pep pe1 p1p p2 1ep 1e1 2p 3 (in different lines)
HOW?
First of all, generate all the binaries of the length equal to the length of the input string.
Binaries -
000 -> pep
001 -> pe1
010 -> p1p
011 -> p2
100 -> 1ep
101 -> 1e1
110 -> 2p
111 -> 3
We can observe that whenever the bit is OFF (zero), we will use the character of the string at that position and whenever the bit is ON (one), we will count all the ON (one) bits that are together and then replace them with the count of the ON (one) bits.
The number of abbreviations will be equal to 2^n, where n = length of the string (as the number of binaries with given n is equal to 2^n ).
In the above example n = 3, therefore the number of abbreviations will be 8 (2^3 = 8).
We can see that this question is like the subsequence problem, we must maintain one more variable which will count the characters that were not included in the subsequence.
For better understanding of the question, watch part of the video lecture. Use recursion as suggested in the video.
Approach:
Let's try to draw the recursion tree diagram for the word, "pep".
In recursion diagram, (a | b | c) a represents the test string, b represents the answer so far and c represents the count.
In the above diagram, (pep|.|0) has two options, either it can include the first p in the answer or not.
If it includes the p in the answer then p is concatenated in the answer so far string and count remains 0.
Then at (pep|p|0), we further explore the options for character e.
It has two options, either it can include e in the answer or not.
If it includes e in the answer then e is concatenated in the answer so far string and count remains 0.
Then at (pep|pe|0), we further explore the options for character p (second p).
It has two options, either it can include p in the answer or not.
If it includes p in the answer then p is concatenated in the answer so far string and count remains 0.
Since we have reached the end of the string, and the count is 0, therefore, the asf i.e. pep is the first possible output.
Then we come back at (pep|pe|0) and explore the path if the second p is not added in the asf.
In this case, p will not be added in psf and therefore count will become 1.
And again, we have reached the end of the string, but count is 1 this time, therefore, this count will be concatenated at the end of the asf, which will give us the next possible output, pe1.
We have explored both the possibilities via (pep|pe|0) therefore, we go back at (pep|p|0), and see what happens if e was not added to asf.
First of all count becomes 1, and we reach (pep|p|1).
Then at (pep|p|1), we further explore the options for character p (second p).
It has two options, either it can include p in the answer or not.
If p is to be included in the answer then we see that our previous count is not 0, so we concatenate the previous count in the asf and then second p.
Since we have reached the end of the string, and the count is 0, therefore, the asf i.e. p1p is the next possible output.
Then we come back at (pep|p|1) and explore the path if the second p is not added in the asf.
In this case, p will not be added in psf and therefore count will become 2.
And again, we have reached the end of the string, but count is 2 this time, therefore, this count will be concatenated at the end of the asf, which will give us the next possible output, p2.
We have explored both the possibilities via (pep|p|1) therefore; we go back at (pep|p|0).
(pep|p|0) has also explored both the options, if "e" were added or not) therefore; we go back at (pep|.|0).
At (pep|.|0), now we explore the possibilities of, if first p were not added in the asf.
If "p" is not added in the answer so far then count becomes 1.
Then at (pep|.|1), we further explore the options for character e.
It has two options, either it can include e in the answer or not.
If it includes e in the answer then e is concatenated with the current count in the answer so far string and count is set to 0.
Then at (pep|1e|0), we further explore the options for character p (second p).
It has two options, either it can include p in the answer or not.
If it includes p in the answer then p is concatenated in the answer so far string and count remains 0.
Since we have reached the end of the string, and the count is 0, therefore, the asf i.e. 1ep is the next possible output.
Then we come back at (pep|1e|0) and explore the path if the second p is not added in the asf.
In this case, p will not be added in psf and therefore count will become 1. And again, we have reached the end of the string, but count is 1 this time, therefore, this count will be concatenated at the end of the asf, which will give us the next possible output, 1e1.
We have explored both the possibilities via (pep|1e|0) therefore, we go back at (pep|.|1), and see what happens if e was not added to asf.
Then at (pep|.|2), we further explore the options for character p (second p).
It has two options, either it can include p in the answer or not.
If p is to be included in the answer then we see that our previous count is not 0, so we concatenate the previous count (2) in the asf and then second p.
Since we have reached the end of the string, and the count is 0, therefore, the asf i.e. 2p is the next possible output.
Then we come back at (pep|.|2) and explore the path if the second p is not added in the asf.
In this case, p will not be added in psf and therefore count will become 3. And again, we have reached the end of the string, but count is 3 this time, therefore, this count will be concatenated at the end of the asf (empty at this stage), which will give us the next possible output, 3.
We have explored both the possibilities via (pep|.|2) therefore; we go back at (pep|.|1).
(pep|.|1) has also explored both the options, if "e" were added or not) therefore; we go back at (pep|.|0).
At (pep|.|0), we have explored both the possibilities that is if first p were not added in the asf.
For a much better and clearer understanding of the recursion diagram, watch part of the lecture video.
Let's try to code this!
import java.util.*;
public class Main {
public static void solution(String str, String asf,int count, int pos){
if(pos == str.length()){
if(count > 0){
asf += count;
}
System.out.println(asf);
return;
}
solution(str, asf + (count > 0 ? count : "" ) + str.charAt(pos), 0, pos + 1); //yes call -> including curr char
solution(str, asf, count + 1, pos + 1); //not including curr char -> just converting letters to a number
}
}
java;
true";
Code Explained:
SIGNATURE of the function: public static void solution (String str, String asf, int count, int pos)
str -Input string
asf - String that stores the answer so far, that is till index pos at different levels.
count - store the count of characters that were not included in the subsequence just before the pos index.
pos - current index.
We will make two calls at each level -
Call Yes - Include the character at index pos in asf
Call No - Do not include the character at index pos in asf.
When we make a NO CALL, we increase the pos variable and not include anything in the asf. We will also increase the count variable as we are not including the current character in answer.
When we make a YES CALL, we will check whether the count is more than zero. If the count is more than zero we will add the count and the character at pos index else we will just add the character at pos index. Also, we will make the count variable equal to zero. We are adding the count to the asf as we have to include the characters that we did not add earlier.
We will make a YES call before NO call because of the order of output.
Base case: We will return when pos will be equal to length of the string. Before returning we will print the asf. If the count will be greater than zero, we will append the count to the asf before printing it.
Watch this part of the video lecture for better understanding.
Complexities:
Time Complexity:
O(2^N)
Where N = length of the input string.
As we are making two calls Yes / No at every index until our pos index is equal to the length of the string, therefore the complexity will be exponential and equal to 2 ^ N.
Space Complexity:
O(N)
Where N = length of the input string.
We can observe that the maximum depth of the recursion tree any time is N. Therefore, the max space occupied at any time will be equal to the N. In the post order, the occupied space in the recursion stack will be freed so the space occupied will not exceed N.
We hope that this article was helpful. If somehow you are finding it difficult to understand this problem then we advise you to watch our video lecture of this problem.
Trust me it will just get easier to understand after you have watched the solution video.
You can contact us via our website. Doubts, suggestions and feedback are always welcomed.
It is also advised that you follow the sequence of modules and questions which is there on our website.
Keep practicing more and more problems daily. Meditate enough on each step of each problem
All the best for an exciting future!
Happy Coding!
