Last Updated on March 28, 2022 by Ria Pathak
CONCEPTS USED:
Recursion
DIFFICULTY LEVEL:
Medium
PROBLEM STATEMENT(SIMPLIFIED):
Given two strings
S1andS2, print the count of all theirInterleaving Strings.
NOTE:
Interleaving Stringis a string that has the same order that of individual strings. This property should be maintained in theInterleaving StringsofS1andS2.
- And all characters from
S1andS2should be present in theirInterleaving Strings.
For Example:
Input : ab cd
Output : 6
Explanation : [abcd, acbd, acdb, cabd, cadb, cdab]
All these are valid Interleaving Strings because original order is preserved in each and every string.
While [abdc, bacd, bcda, adcb] are some of the non-interleaving strings.See original problem statement here
Can we use Recursion here ?
Yes,
Recursionseem to be a great option whenever we need to find different combinations.
SOLVING APPROACH:
Initialize an empty string
strand recursively keep adding characters one after the other either from the first string or the other string till both the strings become exhausted.This is done recursively, where choosing a character from both the strings can be done in
2ways, so it takesExponential Time Complexity.
SOLUTIONS:
#include <stdio.h>
int cnt ;
//Function for counting all interleavings
void countIlsRecur (int m,int n){
/* Base case: If all characters of str1 and str2 have been
included in output string, then print the output string */
if (m == 0 && n == 0){
//cout << iStr << endl;
cnt++;
}
/* If some characters of str1 are left to be included, then
include the first character from the remaining characters
and recur for rest */
if (m > 0) {
//iStr[i] = str1[0];
countIlsRecur (m - 1, n);
}
/* If some characters of str2 are left to be included, then
include the first character from the remaining characters
and recur for rest */
if (n > 0) {
//iStr[i] = str2[0];
countIlsRecur(m,n - 1);
}
}
int main(){
int t;
scanf("%d",&t);
while(t--){
char str1[100],str2[100];
scanf("%s",str1);
scanf("%s",str2);
countIlsRecur(strlen(str1),strlen(str2));
printf("%d\n",cnt);
cnt = 0;
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int countt = 0;
void interleaving(int a,int b){
/* If some characters of s1 are left to be included, then
include the first character from the remaining characters
and recur for rest */
if(a > 0){
interleaving(a-1,b);
}
/* If some characters of s2 are left to be included, then
include the first character from the remaining characters
and recur for rest */
if(b > 0){
interleaving(a,b-1);
}
/* Base case: If all characters of s1 and s2 have been
included in output string */
if(a == 0 && b == 0){
countt++;
}
}
int main(){
int t;cin>>t;
while(t--){
string s1,s2;
cin>>s1>>s2;
int l1 = s1.size();
int l2 = s2.size();
interleaving(l1,l2);
cout<<countt<<"\n";
countt=0;
}
return 0;
}
import java.util.*;
import java.io.*;
public class Main {
public static int countt = 0;
static void interleaving(int a,int b){
/* If some characters of s1 are left to be included, then
include the first character from the remaining characters
and recur for rest */
if(a > 0){
interleaving(a-1,b);
}
/* If some characters of s2 are left to be included, then
include the first character from the remaining characters
and recur for rest */
if(b > 0){
interleaving(a,b-1);
}
/* Base case: If all characters of s1 and s2 have been
included in output string */
if(a == 0 && b == 0){
countt++;
}
}
public static void main(String args[]) throws IOException {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t!=0){
String s1 = sc.next();
String s2 = sc.next();
int l1 = s1.length();
int l2 = s2.length();
interleaving(l1,l2);
System.out.println(countt);
countt=0;
t--;
}
}
}
countt = 0 def interleaving( a, b): global countt if(a > 0): interleaving(a - 1, b) if(b > 0): interleaving(a, b - 1) if(a == 0 and b == 0): countt += 1 for _ in range(int(input())): s1, s2 = input().split() l1, l2 = len(s1), len(s2) interleaving(l1, l2) print(countt) countt = 0
[forminator_quiz id="986"]
This article tried to discuss the concept of Recursion. Hope this blog helps you understand and solve the problem. To practice more problems on Recursion you can check out MYCODE | Competitive Programming.