Posted on by Kalkicode
Code Backtracking

# Print all interleavings of two strings

The problem we're addressing is to generate and print all possible interleavings of two given strings. An interleaving of two strings is a sequence of characters that maintains the relative order of characters from both strings. For example, given the strings "abc" and "xy", the possible interleavings are "xyabc", "xaybc", "axybc", "xabyc", "axbyc", "abxyc", "xabcy", "axbcy", "abxcy", and "abcxy".

## Problem Statement and Description

Given two strings, we want to find and print all the interleaved sequences of characters from these two strings while preserving their original order. This means that each character in the output sequence must either come from the first string or the second string, and their order should be maintained as they appear in the input strings.

## Idea to Solve the Problem

To solve this problem, we can use a recursive approach. The idea is to iterate through each character in the input strings and consider two possibilities: either we choose the character from the first string or from the second string. We recursively explore all possibilities by appending the chosen character to the result and moving to the next position in the result and the corresponding string.

## Pseudocode

``````allInterleavings(a, b, result, n, m, index):
if n equals -1 and m equals -1:
print result
else:
if n >= 0:
result[index] = a[n]
allInterleavings(a, b, result, n - 1, m, index - 1)
if m >= 0:
result[index] = b[m]
allInterleavings(a, b, result, n, m - 1, index - 1)

printResult(a, b):
n = length of a
m = length of b
if n equals 0 or m equals 0:
return
result = array of characters of size n + m + 1
result[n + m] = '\0'
allInterleavings(a, b, result, n - 1, m - 1, n + m - 1)``````

## Algorithm Explanation

1. `allInterleavings(a, b, result, n, m, index)` is the main recursive function. It takes the two input strings `a` and `b`, the current `result` being constructed, the current indices `n` and `m` for the respective strings, and the current `index` in the result being populated.

2. When both `n` and `m` become -1, it indicates that we have considered all characters from both strings, and we print the current result.

3. Otherwise, if `n` is greater than or equal to 0, we choose the character at index `n` from string `a` and recursively call `allInterleavings` with the next index and decremented `n`.

4. Similarly, if `m` is greater than or equal to 0, we choose the character at index `m` from string `b` and recursively call `allInterleavings` with the next index and decremented `m`.

5. The function `printResult(a, b)` calculates the lengths of the input strings `a` and `b`. If either of them has a length of 0, there is nothing to interleave, so we return.

6. An array `result` of characters is created to store the current interleaved sequence. The last element of the array is set to '\0' to terminate the string.

7. We call `allInterleavings` with the initial indices and lengths to start generating the interleavings.

## Code Solution

``````/*
C program for
Print all interleavings of two strings
*/
#include <stdio.h>

#include <string.h>

void allInterleavings(
char a[],
char b[],
char result[],
int n,
int m,
int index)
{
if (n == -1 && m == -1)
{
// When need to print element
printf("\n %s", result);
}
else
{
if (n >= 0)
{
// When n greater than -1
// Assign the n position character value to result
// index indicate position
result[index] = a[n];
// Find interleaving subsequence using recursion
allInterleavings(a, b, result, n - 1, m, index - 1);
}
if (m >= 0)
{
// When m greater than -1
// Assign the m position character value to result
// index indicate position
result[index] = b[m];
// Find interleaving subsequence using recursion
allInterleavings(a, b, result, n, m - 1, index - 1);
}
}
}
// Handles the request of printing the interleaving subsequence
void printResult(char a[], char b[])
{
int n = strlen(a);
int m = strlen(b);
if (n == 0 || m == 0)
{
return;
}
// Use to collect resultant character
char result[n + m + 1];
// Terminate character
result[n + m] = '\0';
printf("\n Given string (%s,%s)", a, b);
// print result
allInterleavings(a, b, result, n - 1, m - 1, n + m - 1);
}
int main()
{
char a1[] = "abc";
char b1[] = "xy";
char a2[] = "code";
char b2[] = "x";
// Test
printResult(a1, b1);
printResult(a2, b2);
return 0;
}``````

#### Output

`````` Given string (abc,xy)
xyabc
xaybc
axybc
xabyc
axbyc
abxyc
xabcy
axbcy
abxcy
abcxy
Given string (code,x)
xcode
cxode
coxde
codxe
codex``````
``````/*
Java program for
Print all interleavings of two strings
*/
public class Interleaving
{
public void allInterleavings(
String a,
String b,
String result,
int n, int m)
{
if (n == -1 && m == -1)
{
// When need to print element
System.out.print("\n " + result);
}
else
{
if (n >= 0)
{
// When n greater than -1
// add the n position character value to result
// Find interleaving subsequence using recursion
allInterleavings(a, b, a.charAt(n) + result, n - 1, m);
}
if (m >= 0)
{
// When m greater than -1
// Add the m position character value to result
// Find interleaving subsequence using recursion
allInterleavings(a, b, b.charAt(m) + result, n, m - 1);
}
}
}
// Handles the request of printing the interleaving subsequence
public void printResult(String a, String b)
{
int n = a.length();
int m = b.length();
if (n == 0 || m == 0)
{
return;
}
System.out.print("\n Given string (" + a + "," + b + ")");
// print result
allInterleavings(a, b, "", n - 1, m - 1);
}
public static void main(String[] args)
{
String a1 = "abc";
String b1 = "xy";
String a2 = "code";
String b2 = "x";
// Test
}
}``````

#### Output

`````` Given string (abc,xy)
xyabc
xaybc
axybc
xabyc
axbyc
abxyc
xabcy
axbcy
abxcy
abcxy
Given string (code,x)
xcode
cxode
coxde
codxe
codex``````
``````// Include header file
#include <iostream>
#include <string>

using namespace std;
/*
C++ program for
Print all interleavings of two strings
*/
class Interleaving
{
public: void allInterleavings(
string a,
string b,
string result,
int n,
int m)
{
if (n == -1 && m == -1)
{
// When need to print element
cout << "\n " << result;
}
else
{
if (n >= 0)
{
// When n greater than -1
// add the n position character value to result
// Find interleaving subsequence using recursion
this->allInterleavings(a, b,
(a[n])  +  result, n - 1, m);
}
if (m >= 0)
{
// When m greater than -1
// Add the m position character value to result
// Find interleaving subsequence using recursion
this->allInterleavings(a, b,
(b[m])  +  result, n, m - 1);
}
}
}
// Handles the request of printing the interleaving subsequence
void printResult(string a, string b)
{
int n = a.length();
int m = b.length();
if (n == 0 || m == 0)
{
return;
}
cout << "\n Given string (" << a << "," << b << ")";
// print result
this->allInterleavings(a, b, "", n - 1, m - 1);
}
};
int main()
{
string a1 = "abc";
string b1 = "xy";
string a2 = "code";
string b2 = "x";
// Test
return 0;
}``````

#### Output

`````` Given string (abc,xy)
xyabc
xaybc
axybc
xabyc
axbyc
abxyc
xabcy
axbcy
abxcy
abcxy
Given string (code,x)
xcode
cxode
coxde
codxe
codex``````
``````// Include namespace system
using System;
/*
Csharp program for
Print all interleavings of two strings
*/
public class Interleaving
{
public void allInterleavings(
String a,
String b,
String result,
int n,
int m)
{
if (n == -1 && m == -1)
{
// When need to print element
Console.Write("\n " + result);
}
else
{
if (n >= 0)
{
// When n greater than -1
// add the n position character value to result
// Find interleaving subsequence using recursion
this.allInterleavings(a, b, a[n] + result, n - 1, m);
}
if (m >= 0)
{
// When m greater than -1
// Add the m position character value to result
// Find interleaving subsequence using recursion
this.allInterleavings(a, b, b[m] + result, n, m - 1);
}
}
}
// Handles the request of printing the interleaving subsequence
public void printResult(String a, String b)
{
int n = a.Length;
int m = b.Length;
if (n == 0 || m == 0)
{
return;
}
Console.Write("\n Given string (" + a + "," + b + ")");
// print result
this.allInterleavings(a, b, "", n - 1, m - 1);
}
public static void Main(String[] args)
{
String a1 = "abc";
String b1 = "xy";
String a2 = "code";
String b2 = "x";
// Test
}
}``````

#### Output

`````` Given string (abc,xy)
xyabc
xaybc
axybc
xabyc
axbyc
abxyc
xabcy
axbcy
abxcy
abcxy
Given string (code,x)
xcode
cxode
coxde
codxe
codex``````
``````package main
import "fmt"
/*
Go program for
Print all interleavings of two strings
*/

func allInterleavings(a string, b string, result string, n int, m int) {
if n == -1 && m == -1 {
// When need to print element
fmt.Print("\n ", result)
} else {
if n >= 0 {
// When n greater than -1
// add the n position character value to result
// Find interleaving subsequence using recursion
allInterleavings(a, b, string(a[n]) + result, n - 1, m)
}
if m >= 0 {
// When m greater than -1
// Add the m position character value to result
// Find interleaving subsequence using recursion
allInterleavings(a, b, string(b[m]) + result, n, m - 1)
}
}
}
// Handles the request of printing the interleaving subsequence
func printResult(a, b string) {
var n int = len(a)
var m int = len(b)
if n == 0 || m == 0 {
return
}
fmt.Print("\n Given string (", a, ",", b, ")")
// print result
allInterleavings(a, b, "", n - 1, m - 1)
}
func main() {
var a1 string = "abc"
var b1 string = "xy"
var a2 string = "code"
var b2 string = "x"
// Test
printResult(a1, b1)
printResult(a2, b2)
}``````

#### Output

`````` Given string (abc,xy)
xyabc
xaybc
axybc
xabyc
axbyc
abxyc
xabcy
axbcy
abxcy
abcxy
Given string (code,x)
xcode
cxode
coxde
codxe
codex``````
``````<?php
/*
Php program for
Print all interleavings of two strings
*/
class Interleaving
{
public	function allInterleavings(\$a, \$b, \$result, \$n, \$m)
{
if (\$n == -1 && \$m == -1)
{
// When need to print element
echo("\n ".\$result);
}
else
{
if (\$n >= 0)
{
// When n greater than -1
// add the n position character value to result
// Find interleaving subsequence using recursion
\$this->allInterleavings(\$a, \$b,
strval(\$a[\$n]).\$result, \$n - 1, \$m);
}
if (\$m >= 0)
{
// When m greater than -1
// Add the m position character value to result
// Find interleaving subsequence using recursion
\$this->allInterleavings(\$a, \$b,
strval(\$b[\$m]).\$result, \$n, \$m - 1);
}
}
}
// Handles the request of printing the interleaving subsequence
public	function printResult(\$a, \$b)
{
\$n = strlen(\$a);
\$m = strlen(\$b);
if (\$n == 0 || \$m == 0)
{
return;
}
echo("\n Given string (".\$a.",".\$b.")");
// print result
\$this->allInterleavings(\$a, \$b, "", \$n - 1, \$m - 1);
}
}

function main()
{
\$a1 = "abc";
\$b1 = "xy";
\$a2 = "code";
\$b2 = "x";
// Test
}
main();``````

#### Output

`````` Given string (abc,xy)
xyabc
xaybc
axybc
xabyc
axbyc
abxyc
xabcy
axbcy
abxcy
abcxy
Given string (code,x)
xcode
cxode
coxde
codxe
codex``````
``````/*
Node JS program for
Print all interleavings of two strings
*/
class Interleaving
{
allInterleavings(a, b, result, n, m)
{
if (n == -1 && m == -1)
{
// When need to print element
process.stdout.write("\n " + result);
}
else
{
if (n >= 0)
{
// When n greater than -1
// add the n position character value to result
// Find interleaving subsequence using recursion
this.allInterleavings(a, b,
a.charAt(n) + result, n - 1, m);
}
if (m >= 0)
{
// When m greater than -1
// Add the m position character value to result
// Find interleaving subsequence using recursion
this.allInterleavings(a, b,
b.charAt(m) + result, n, m - 1);
}
}
}
// Handles the request of printing the interleaving subsequence
printResult(a, b)
{
var n = a.length;
var m = b.length;
if (n == 0 || m == 0)
{
return;
}
process.stdout.write("\n Given string (" + a + "," + b + ")");
// print result
this.allInterleavings(a, b, "", n - 1, m - 1);
}
}

function main()
{
var a1 = "abc";
var b1 = "xy";
var a2 = "code";
var b2 = "x";
// Test
}
main();``````

#### Output

`````` Given string (abc,xy)
xyabc
xaybc
axybc
xabyc
axbyc
abxyc
xabcy
axbcy
abxcy
abcxy
Given string (code,x)
xcode
cxode
coxde
codxe
codex``````
``````#    Python 3 program for
#    Print all interleavings of two strings
class Interleaving :
def allInterleavings(self, a, b, result, n, m) :
if (n == -1 and m == -1) :
#  When need to print element
print("\n ", result, end = "")
else :
if (n >= 0) :
#  When n greater than -1
#  add the n position character value to result
#  Find interleaving subsequence using recursion
self.allInterleavings(a, b, str(a[n]) + result, n - 1, m)

if (m >= 0) :
#  When m greater than -1
#  Add the m position character value to result
#  Find interleaving subsequence using recursion
self.allInterleavings(a, b, str(b[m]) + result, n, m - 1)

#  Handles the request of printing the interleaving subsequence
def printResult(self, a, b) :
n = len(a)
m = len(b)
if (n == 0 or m == 0) :
return

print("\n Given string (", a ,",", b ,")", end = "")
#  print result
self.allInterleavings(a, b, "", n - 1, m - 1)

def main() :
a1 = "abc"
b1 = "xy"
a2 = "code"
b2 = "x"
#  Test

if __name__ == "__main__": main()``````

#### Output

`````` Given string ( abc , xy )
xyabc
xaybc
axybc
xabyc
axbyc
abxyc
xabcy
axbcy
abxcy
abcxy
Given string ( code , x )
xcode
cxode
coxde
codxe
codex``````
``````#    Ruby program for
#    Print all interleavings of two strings
class Interleaving
def allInterleavings(a, b, result, n, m)
if (n == -1 && m == -1)
#  When need to print element
print("\n ", result)
else

if (n >= 0)
#  When n greater than -1
#  add the n position character value to result
#  Find interleaving subsequence using recursion
self.allInterleavings(a, b, a[n].to_s + result, n - 1, m)
end

if (m >= 0)
#  When m greater than -1
#  Add the m position character value to result
#  Find interleaving subsequence using recursion
self.allInterleavings(a, b, b[m].to_s + result, n, m - 1)
end

end

end

#  Handles the request of printing the interleaving subsequence
def printResult(a, b)
n = a.length
m = b.length
if (n == 0 || m == 0)
return
end

print("\n Given string (", a ,",", b ,")")
#  print result
self.allInterleavings(a, b, "", n - 1, m - 1)
end

end

def main()
a1 = "abc"
b1 = "xy"
a2 = "code"
b2 = "x"
#  Test
end

main()``````

#### Output

`````` Given string (abc,xy)
xyabc
xaybc
axybc
xabyc
axbyc
abxyc
xabcy
axbcy
abxcy
abcxy
Given string (code,x)
xcode
cxode
coxde
codxe
codex``````
``````/*
Scala program for
Print all interleavings of two strings
*/
class Interleaving()
{
def allInterleavings(
a: String,
b: String,
result: String,
n: Int,
m: Int): Unit = {
if (n == -1 && m == -1)
{
// When need to print element
print("\n " + result);
}
else
{
if (n >= 0)
{
// When n greater than -1
// add the n position character value to result
// Find interleaving subsequence using recursion
allInterleavings(a, b,
a.charAt(n).toString() + result, n - 1, m);
}
if (m >= 0)
{
// When m greater than -1
// Add the m position character value to result
// Find interleaving subsequence using recursion
allInterleavings(a, b,
b.charAt(m).toString() + result, n, m - 1);
}
}
}
// Handles the request of printing the interleaving subsequence
def printResult(a: String, b: String): Unit = {
var n: Int = a.length();
var m: Int = b.length();
if (n == 0 || m == 0)
{
return;
}
print("\n Given string (" + a + "," + b + ")");
// print result
allInterleavings(a, b, "", n - 1, m - 1);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Interleaving = new Interleaving();
var a1: String = "abc";
var b1: String = "xy";
var a2: String = "code";
var b2: String = "x";
// Test
}
}``````

#### Output

`````` Given string (abc,xy)
xyabc
xaybc
axybc
xabyc
axbyc
abxyc
xabcy
axbcy
abxcy
abcxy
Given string (code,x)
xcode
cxode
coxde
codxe
codex``````
``````/*
Swift 4 program for
Print all interleavings of two strings
*/
class Interleaving
{
func allInterleavings(_ a: String,
_ b: String,
_ result: String,
_ n: Int,
_ m: Int)
{
if (n == -1 && m == -1)
{
// When need to print element
print("\n ", result, terminator: "");
}
else
{
if (n >= 0)
{
// When n greater than -1
// add the n position character value to result
// Find interleaving subsequence using recursion
self.allInterleavings(a, b,
String(Array(a)[n]) + result, n - 1, m);
}
if (m >= 0)
{
// When m greater than -1
// Add the m position character value to result
// Find interleaving subsequence using recursion
self.allInterleavings(a, b,
String(Array(b)[m]) + result, n, m - 1);
}
}
}
// Handles the request of printing the interleaving subsequence
func printResult(_ a: String, _ b: String)
{
let n: Int = a.count;
let m: Int = b.count;
if (n == 0 || m == 0)
{
return;
}
print("\n Given string (", a ,",", b ,")", terminator: "");
// print result
self.allInterleavings(a, b, "", n - 1, m - 1);
}
}
func main()
{
let a1: String = "abc";
let b1: String = "xy";
let a2: String = "code";
let b2: String = "x";
// Test
}
main();``````

#### Output

`````` Given string ( abc , xy )
xyabc
xaybc
axybc
xabyc
axbyc
abxyc
xabcy
axbcy
abxcy
abcxy
Given string ( code , x )
xcode
cxode
coxde
codxe
codex``````
``````/*
Kotlin program for
Print all interleavings of two strings
*/
class Interleaving
{
fun allInterleavings(
a: String,
b: String,
result: String,
n: Int, m: Int): Unit
{
if (n == -1 && m == -1)
{
// When need to print element
print("\n " + result);
}
else
{
if (n >= 0)
{
// When n greater than -1
// add the n position character value to result
// Find interleaving subsequence using recursion
this.allInterleavings(a, b,
a.get(n).toString() + result, n - 1, m);
}
if (m >= 0)
{
// When m greater than -1
// Add the m position character value to result
// Find interleaving subsequence using recursion
this.allInterleavings(a, b,
b.get(m).toString() + result, n, m - 1);
}
}
}
// Handles the request of printing the interleaving subsequence
fun printResult(a: String, b: String): Unit
{
val n: Int = a.length;
val m: Int = b.length;
if (n == 0 || m == 0)
{
return;
}
print("\n Given string (" + a + "," + b + ")");
// print result
this.allInterleavings(a, b, "", n - 1, m - 1);
}
}
fun main(args: Array < String > ): Unit
{
val a1: String = "abc";
val b1: String = "xy";
val a2: String = "code";
val b2: String = "x";
// Test
}``````

#### Output

`````` Given string (abc,xy)
xyabc
xaybc
axybc
xabyc
axbyc
abxyc
xabcy
axbcy
abxcy
abcxy
Given string (code,x)
xcode
cxode
coxde
codxe
codex``````

## Time Complexity

The time complexity of this algorithm depends on the number of recursive calls made. In the worst case, the algorithm will explore all possible interleavings, which is exponential in the sum of the lengths of the two input strings. Therefore, the time complexity is O(2^(n+m)), where n and m are the lengths of the two input strings.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post