Hello, and welcome to a wonderful series of competitive programming with python where we are learning Recursion. This is part - 2 of the series and we have already learned the basics of recursion and performed some basics questions which I hope helped you to build a good base with recursion. If you have not gone through the previous part I will request you to please have a look even if you are familiar with the Recursion. In this part, we will take the series forward and do some good levels of questions that will help you to enhance your observation and thinking skills to approach a particular problem.
Table of Contents
1) Tower of Hanoi
You must have encountered this problem somewhere. It is one of the famous interview questions in recursion. so let us understand the problem statement.
Problem Statement - Given Three rods and N number of the disk. Your target is to move all the disks from the source rod to the destination rod, obeying some simple rules.
- You can only move one disk at a time
- Rod contains disk in form of the stack so you can only remove the disk from the top.
- A larger disk cannot be placed on top of a small disk.
What we understand ~ By reading the problem statement it is clear to us that we have three rods named as the source, destination, and helper. Now we are supposed to move all the disks from the source in form of the same arrangement to the destination rod with the help of one temporary or helper rod by following the above three rules.
Let us take one example to explore and understand the problem so we can reach out to a solution.
Example ~ Observe the below figure which is our problem statement.
Now let's say we have 3 disks in the source rod and we have to move it to the destination so if we solve this puzzle manually on paper then how the steps will look like. As I write the steps below try performing them on paper while reading. Assume source as A, helper as B, and destination as C.
- move 1st disk from A to C
- move 2nd disk from A to B
- move 1st disk from C to B
- move 3rd disk from A to C
- move 1st disk from B to A
- move 2nd disk from B to C
- move 1st disk from A to C
Recursive Approach ~ So if you observe the steps carefully so what basically solution can be summarized in three steps.
- If in anyhow we can move N-1 disk from source to helper using destination as a middle man.
- Now shift the last Nth disk from source to destination.
- Then shift the remaining N-1 disk from helper to destination using source as a middle man.
So we can build this recursive solution very easily in three lines of code by only changing source, and destination correctly as we discussed. In the first step, our destination is the helper rod to move the N-1 disk and the middle man is the destination rod. And the same step needs to alternate for the third step. Write the code as per discussed steps.
def TowerOfHanoi(n, source, helper, dest):
if n == 0:
return
#move n-1 disk from source to helper using dest
TowerOfHanoi(n-1, source, dest, helper)
#move last disk from src to dest
print("move {} disk from {} to {}".format(n, source, dest))
#move n-1 disk from helper to dest using source
TowerOfHanoi(n-1, helper, source, dest)
n = 3
TowerOfHanoi(n, "A", "B", "C")
2) Print Keypad Combinations
Hope that the first question is completely clear to you. This is an interesting Leetcode problem statement. The problem statement comes in the medium category. Before smartphones on keypad phones and telephones, text and numbers are placed on the same key. For example on key 2 "ABC" string is present.
Problem Statement ~ Given the n digit number print all the possible combinations of words that can be formed by pressing that key.
Example
INPUT = 23
OUTPUT = ['AD', 'AE', 'AF', 'BD', 'BE', 'BF', 'CD', 'CE', 'CF']
Explanation
"ABC" string is present on key 2 and "DEF" is present on key 3. So, using these two strings of length three we can form six different combinations as listed.
I hope that the problem statement is clear to you. If you have any doubt then just search the heading of problem in google and the Leetcode problem statement will open. So let's discuss how we can attempt this question.
Recursive Approach
we have studied that whenever we have a number problem then the first thing we think of using modulus and division operator when said to find all possible cases. After saying just this much you should catch the solution that how our recursive tree will look like. We will access each digit from the number and access its corresponding string option. Now we will apply the loop for each character in the options string make the recursive call with a remaining number and combine each character in the output. We are accessing the last digit each time so the first option character will join and then the remaining output string. Have a look at the recursive binary tree below.
Now can we write the code using the above diagram? just a request that without seeing code try to write concerning the recursive tree.
def keypadCombinations(n, output, options):
if n == 0:
print(output)
dig = n % 10
s = options[dig]
#comb with each char in key chars
for i in s:
keypadCombinations(n//10, i+output, options)
n = 23
options = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
keypadCombinations(n, "", options)
3) Count Ways to reach Nth stair
One more interesting leetcode problem from the Easy category. Now you may be wondering after the medium category why are we again picking an easy category question. I am picking this problem after medium because this is also below to binary recursive tree and I want this tree that you build yourself. So let's understand the problem statement.
Problem Statement ~ Given N number of steps we can reach the top in N steps. we are given that we can take 1 or 2 steps at a time. Count the distinct combinations of one and two by using which you can reach the top.
Example
INPUT = 3
OUTPUT = 3
Explanation ~ There are three different combinations to reach the top of stairs
1 step + 1 step + 1 step = 3
1 step + 2 step = 3
2 step + 1 step = 3
Recursive Approach
I hope that you can think over the approach to solving this. Now how we can solve this is to think what answer we know so we know that we can climb 1 or 2 steps. It means that if we have 1 step to climb then we only have 1 way to reach it. If we have 2 steps left to climb then there are only 2 ways to reach there by taking a combination of 1 and single 2. So we can recursively call the function by adding N-1 and N-2 steps to reach the top. Observe the below recursive tree when we have 4 stairs.
def stairCase(n):
if n == 0 or n == 1:
return 1
elif n == 2:
return 2
else:
return stairCase(n-1) + stairCase(n-2)
n = 4
print(stairCase(n))
4) Print all possible decodings of Digit Sequence
One of medium category very interesting problem statement. Given a string of numbers when 1 represents 'A', 2 represents 'B', and so on. Your task is to print all possible alphabetical strings that can be obtained from a given string of numbers.
Example
INPUT = "1123"
OUTPUT = ["aabc", "kbc", "alc", "aaw", "kw"]
Explanation ~ The string can be split into the following forms
1) “1123” = “1” + “1” + “2” + “3” = aabc 2) "1123" = "11" + "2" + "3" = kbc 3) "1123" = "1" + "12" + "3" = alc 4) "1123" = "1" + "1" + "23" = aaw 5) "1123" = "11" + "23" = kw
Recursive Approach
We can easily build a recursive tree in such a way that each time we have two choices to split the string. Alphabets are between 1 to 26 so we can only form numbers between this range. So what we will do is each time a single digit is valid so first, we will take a single digit, convert it to a character and make a recursive call with the remaining string with joining that character with output(initial output parameter in the function is empty). Now access the two-digit from string and while converting to integer check that is it between 10 to 26 inclusively. If true then make a recursive call with the remaining string. The approach will be more clear when you look at below recursive tree.
Code ~ Writing code using a solved recursive tree is very easy.
def decodeString(inp, output):
if inp == "":
print(output)
return
ch1 = chr(int(inp[0])+ord('a') - 1) #single digit to chr
decodeString(inp[1:], output+ch1)
b = int(inp[:2])
ch2 = chr(b+ord('a')-1) #double digit in chr
if b>=10 and b<=26: #check is it chr
decodeString(inp[2:], output+ch2)
inp = "1123"
decodeString(inp, "")
5) All permutations of a string
One more interesting problem is finding all the permutations of a string. It also resides in a medium category but after doing this many questions I know that you can make it in a short period. let us take the example to understand what exact output we want
Example
INPUT = "ABC"
OUTPUT = ["ABC", "ACB", "BAC", "BCA", "CAB", "CBA"]
Recursive Approach
A permutation is basically the rearrangement of elements. If I ask in how ways the word "RAM" can be rearranged you will tell me N factorial ways. This means that in the first place you have three characters to place, in the second place we have 2 characters, and on the last one character. Think a little bit about how we can make a recursive tree for this problem. what happens is each character occurs at each position minimum of one number times. So here we have to perform a recursive call in a loop in such a way that whatever input string we got, we have to pick each character, join it with the output string(initially passed as empty), and make a recursive call with the remaining string so each time one character will be removed from the input string and take place in the output string. Finally, when the input string is empty it means one permutation is complete which is our base case. In short, whenever the input string is input, it generates one output. have a look at the below recursive tree for the input string "CBA".
Now you should write the code for this problem.
def StringPermutation(inp, output):
if inp == "":
print(output)
return
for i in range(len(inp)):
StringPermutation(inp[:i]+inp[i+1:], output+inp[i])
inp = "ABC"
StringPermutation(inp, "")
6) Letter Case Permutation
This is one tricky leetcode problem statement where we are given a string of characters and digits and the task is to print all possible permutations of string by changing the case means output string should have permutation with uppercase, and lowercase combination both. observe the below example to understand input and output.
Example
INPUT = "a1b2"
OUTPUT = ['a1b2', 'a1B2', 'A1b2', 'A1B2']
I think an explanation of an example is not required as we have two characters so we can form four combinations by having lowercase and uppercase. Digits should include as it is.
Recursive Approach
We know that whenever we have a sequence data type first task is to think for the first element and how many different ways the first element can come in answer. So, in this problem, it is simply that if the element is a character then it can come once in uppercase form and once in lowercase form. And if it is a digit then the only choice is to join in the output string as it is. So we can make two recursive calls in the If statement if it is a character and one call if it is a digit.
Now I request you to construct your recursive binary tree for the above example finding all possible cases. And I am 100 percent sure that if you construct a tree then writing code is just a minute game.
Code
def letterCasePermutation(inp, output):
if inp == "":
print(output)
return
if inp[0].isalpha():
op1 = output + inp[0].lower()
op2 = output + inp[0].upper()
#make recursive call with lowercase and uppercase
letterCasePermutation(inp[1:], op1)
letterCasePermutation(inp[1:], op2)
else:
#it is digit so single recursive call
op1 = output + inp[0]
letterCasePermutation(inp[1:], op1)
inp = "a1b2"
letterCasePermutation(inp, "")
Practice Questions for You to solve
A] Remove all consecutive characters from a string
Given a string of characters, your task is to return the modified string by removing all the consecutive characters from a string.
Example
INPUT = "aabaa"
OUTPUT = "aba"
Approach ~ we have done similar questions of this type so you have to focus on the first character than on the remaining ones. so what you have to do is pick each character and match it with the next one. If it matches then you have to use a loop and increase an index till where you got character when it does not match. Add a single occurrence of a character in the output string and make a recursive call for the remaining string.
B] Permutation with Case Change
It is a simple problem to one we have done above. Given a string of characters and task is to print all possible permutations of the string by changing its case.
Example
INPUT = "ab"
OUTPUT = ['AB', 'Ab', 'aB', 'ab']
C] Permutation with Spaces
This is also a simple problem belonging to the same type. Given a string, your task is to print all the permutations of it by placing space between the characters.
Example
INPUT = "ABC"
OUTPUT = ["ABC", "AB_C", "A_BC", "A_B_C"]
Take each character and make two recursive calls as you have two choices to include space after character and not to take space.
End Notes
If you have followed this article till here then many congratulations to you. I hope that it helps to think and develop your own approach and it will enforce you to try attempting a new problem and think over it a little bit before seeing a solution. The practice question is for you to attempt which will help build your confidence to think the recursive approach and solve questions on recursion. If you can make all the questions from the practice list or any question then explain the approach in the comment section and if you have doubts related to any question then feel free to post them in the comment section below.
Thanks for your time😊