Problem Description

Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.

An interleaving of two strings s and t is a configuration where s and t are divided into n and m substrings respectively, such that:

s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| <= 1
The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ... Note: a + b is the concatenation of strings a and b.

Link

Solution 1: Dynamic Programming

This problem is a typical dynamic programming problem. We can define a 2D boolean array dp where dp[i][j] indicates whether s3[0:i+j] can be formed by interleaving s1[0:i] and s2[0:j].

Code

func isInterleave(s1 string, s2 string, s3 string) bool {
    m, n := len(s1), len(s2)
    l := len(s3)

    if m + n != l {
        return false
    }
    dp := make([][]bool, m + 1)
    for i := range dp {
        dp[i] = make([]bool, n+1)
    }

    dp[0][0] = true

    for j := 1; j <= n; j++ {
        dp[0][j] = dp[0][j-1] && s3[j-1] == s2[j-1]
    }

    for i := 1; i <= m; i++ {
        dp[i][0] = dp[i-1][0] && s3[i-1] == s1[i-1]
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            dp[i][j] = (dp[i-1][j] && s3[i+j-1] == s1[i-1]) || (dp[i][j-1] && s3[i+j-1] == s2[j-1])
        }
    }
    return dp[m][n]
}

Time Complexity: O(mn)

Space Complexity: O(mn)

Solution 2: Dynamic Programming (Optimized Space)

Based on the previous solution, we can optimize the space complexity to O(n) by using a 1D array instead of a 2D array. we can see that dp[i][j] only depends on dp[i-1][j] and dp[i][j-1], so we can use a single array to store the current row.

When we compute dp[i][j], we need:

dp[i-1][j]: value from previous row, same column
dp[i][j-1]: value from current row, previous column

So in the 1D array, before updating dp[j]

dp[j] stores dp[i-1][j] (previous row)
dp[j-1] stores dp[i][j-1] (current row, already updated)

Code

func isInterleave(s1 string, s2 string, s3 string) bool {
	m, n := len(s1), len(s2)

	if m+n != len(s3) {
		return false
	}

	dp := make([]bool, n+1)
	dp[0] = true

	for j := 1; j <= n; j++ {
		dp[j] = dp[j-1] && s3[j-1] == s2[j-1]
	}

	for i := 1; i <= m; i++ {
		dp[0] = dp[0] && s1[i-1] == s3[i-1]

		for j := 1; j <= n; j++ {
			dp[j] = (dp[j] && s1[i-1] == s3[i+j-1]) ||
				(dp[j-1] && s2[j-1] == s3[i+j-1])
		}
	}
	return dp[n]
}

Time Complexity: O(mn)

Space Complexity: O(n)

Solution 3: DFS

We can also use DFS to solve this problem.

Code

func isInterleave(s1 string, s2 string, s3 string) bool {
	m , n := len(s1), len(s2)
	if m + n != len(s3) {
		return false
	}

	memo := make(map[[2]int]bool)
	var dfs func(i, j int) bool

	dfs = func(i, j int) bool {
		if i == len(s1) && j == len(s2) {
			return true
		}
		key := [2]int{i, j}
		if val, exists := memo[key]; exists {
			return val
		}

		result := false

		k := i + j

		if i < len(s1) && s1[i] == s3[k] {
			result = dfs(i+1,j)
		}
		if !result && j < len(s2) && s2[j] == s3[k] {
			result = dfs(i, j+1)
		}
		memo[key] = result
		return result
	}
	return dfs(0,0)
}

Time Complexity: O(mn)

Space Complexity: O(mn)