Skip to main content

Print all interleavings of two strings

Here given code implementation process.

/*
    C program for
    Print all interleavings of two strings 
*/
// Include header file
#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)
	{
		Interleaving task = new Interleaving();
		String a1 = "abc";
		String b1 = "xy";
		String a2 = "code";
		String b2 = "x";
		// Test
		task.printResult(a1, b1);
		task.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
// 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()
{
	Interleaving *task = new Interleaving();
	string a1 = "abc";
	string b1 = "xy";
	string a2 = "code";
	string b2 = "x";
	// Test
	task->printResult(a1, b1);
	task->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
// 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)
	{
		Interleaving task = new Interleaving();
		String a1 = "abc";
		String b1 = "xy";
		String a2 = "code";
		String b2 = "x";
		// Test
		task.printResult(a1, b1);
		task.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
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()
{
	$task = new Interleaving();
	$a1 = "abc";
	$b1 = "xy";
	$a2 = "code";
	$b2 = "x";
	// Test
	$task->printResult($a1, $b1);
	$task->printResult($a2, $b2);
}
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 task = new Interleaving();
	var a1 = "abc";
	var b1 = "xy";
	var a2 = "code";
	var b2 = "x";
	// Test
	task.printResult(a1, b1);
	task.printResult(a2, b2);
}
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() :
	task = Interleaving()
	a1 = "abc"
	b1 = "xy"
	a2 = "code"
	b2 = "x"
	#  Test
	task.printResult(a1, b1)
	task.printResult(a2, b2)

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() 
	task = Interleaving.new()
	a1 = "abc"
	b1 = "xy"
	a2 = "code"
	b2 = "x"
	#  Test
	task.printResult(a1, b1)
	task.printResult(a2, b2)
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
		task.printResult(a1, b1);
		task.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
/*
    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 task: Interleaving = Interleaving();
	let a1: String = "abc";
	let b1: String = "xy";
	let a2: String = "code";
	let b2: String = "x";
	// Test
	task.printResult(a1, b1);
	task.printResult(a2, b2);
}
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 task: Interleaving = Interleaving();
	val a1: String = "abc";
	val b1: String = "xy";
	val a2: String = "code";
	val b2: String = "x";
	// Test
	task.printResult(a1, b1);
	task.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
Last updated on by Kalkicode




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.

New Comment