Interleaving String Program

Overview

Three strings are given s1, s2, s3. Find if string s3 is interleaving of string.

s3 will be an interleaving of string s1 and s2 if the below condition is satisfied

• s3 contains all characters of s1 and s2 and the order of all characters in individual strings is preserved.

Example

s1: aabcc
s2: dbbca
s3: aadbbcbcac

Output: true

Recursive Solution

Below is the recursive solution for the same

package main

import "fmt"

func main() {
	output := isInterleave("aabcc", "dbbca", "aadbbcbcac")
	fmt.Println(output)

	output = isInterleave("", "", "")
	fmt.Println(output)
}
func isInterleave(s1 string, s2 string, s3 string) bool {
	s1Rune := []rune(s1)
	s2Rune := []rune(s2)
	s3Rune := []rune(s3)

	lenS1 := len(s1Rune)
	lenS2 := len(s2Rune)
	lenS3 := len(s3Rune)

	if lenS1+lenS2 != lenS3 {
		return false
	}

	return isInterleaveUtil(s1Rune, s2Rune, s3Rune, 0, 0, 0, lenS1, lenS2, lenS3)
}

func isInterleaveUtil(s1, s2, s3 []rune, x, y, z, lenS1, lenS2, lenS3 int) bool {
	if x == lenS1 && y == lenS2 && z == lenS3 {
		return true
	}

	if x < lenS1 && z < lenS3 && s1[x] == s3[z] {
		match := isInterleaveUtil(s1, s2, s3, x+1, y, z+1, lenS1, lenS2, lenS3)
		if match {
			return true
		}
	}

	if y < lenS2 && z < lenS3 && s2[y] == s3[z] {
		return isInterleaveUtil(s1, s2, s3, x, y+1, z+1, lenS1, lenS2, lenS3)

	}
	return false
}

Output

true
true

If you will notice the above program many subproblems are computed again and again hence the complexity of the above solution is exponential. Hence we can also use Dynamic Programming here to reduce the overall time complexity.

Here is the program for the same

Dynamic Programming Solution

package main

import "fmt"

func main() {
	output := isInterleave("aabcc", "dbbca", "aadbbcbcac")
	fmt.Println(output)

	output = isInterleave("", "", "")
	fmt.Println(output)
}
func isInterleave(s1 string, s2 string, s3 string) bool {
	s1Rune := []rune(s1)
	s2Rune := []rune(s2)
	s3Rune := []rune(s3)

	lenS1 := len(s1Rune)
	lenS2 := len(s2Rune)
	lenS3 := len(s3Rune)

	if lenS1+lenS2 != lenS3 {
		return false
	}

	interleavingMatrix := make([][]bool, lenS1+1)

	for i := range interleavingMatrix {
		interleavingMatrix[i] = make([]bool, lenS2+1)
	}

	i := 1
	k := 1

	interleavingMatrix[0][0] = true

	for i <= lenS1 && k <= lenS3 {
		if s1Rune[i-1] == s3Rune[k-1] {
			interleavingMatrix[i][0] = true
			i++
			k++
		} else {
			break
		}
	}

	i = 1
	k = 1

	for i <= lenS2 && k <= lenS3 {
		if s2Rune[i-1] == s3Rune[k-1] {
			interleavingMatrix[0][i] = true
			i++
			k++
		} else {
			break
		}
	}

	for i := 1; i <= lenS1; i++ {
		for j := 1; j <= lenS2; j++ {

			if s1Rune[i-1] == s3Rune[i+j-1] {
				interleavingMatrix[i][j] = interleavingMatrix[i-1][j]
			}

			if s2Rune[j-1] == s3Rune[i+j-1] && !interleavingMatrix[i][j] {
				interleavingMatrix[i][j] = interleavingMatrix[i][j-1]
			}

		}
	}

	return interleavingMatrix[lenS1][lenS2]
}

Output

true
true