Interleaving String

Medium

The problem

Return true if s3 can be built by mixing the characters of s1 and s2 together, where the characters of s1 stay in their original order and the characters of s2 stay in their original order. Every character of both strings must be used.

Example 1
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Take "aa" from s1, then "dbbc" from s2, then "bc" from s1, "a" from s2 and "c" from s1.
Example 2
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
No mixing of the two strings can spell s3.
Example 3
Input: s1 = "", s2 = "", s3 = ""
Output: true

Limits

0 ≤ len(s1), len(s2) ≤ 200
0 ≤ len(s3) ≤ 400
All strings have only lowercase English letters

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

After using i characters of s1 and j of s2, the next character of s3 is at index i+j.

The idea

dp[i][j] = (dp[i−1][j] and s1[i−1]==s3[i+j−1]) or (dp[i][j−1] and s2[j−1]==s3[i+j−1]).

Target: O(m·n) time

Go function shape

func isInterleave(s1 string, s2 string, s3 string) bool

Reference solution

Tested with go test. Try it yourself first, then compare.

// IsInterleave: can s3 be formed by weaving s1 and s2 without reordering either?
// dp[i][j] = the first i letters of s1 and j letters of s2 can form the first i+j letters of s3.
func IsInterleave(s1, s2, s3 string) bool {
	if len(s1)+len(s2) != len(s3) {
		return false
	}
	dp := make([][]bool, len(s1)+1)
	for i := range dp {
		dp[i] = make([]bool, len(s2)+1)
	}
	dp[0][0] = true
	for i := 0; i <= len(s1); i++ {
		for j := 0; j <= len(s2); j++ {
			if i > 0 && dp[i-1][j] && s1[i-1] == s3[i+j-1] {
				dp[i][j] = true
			}
			if j > 0 && dp[i][j-1] && s2[j-1] == s3[i+j-1] {
				dp[i][j] = true
			}
		}
	}
	return dp[len(s1)][len(s2)]
}

Read the lesson: 2-D Dynamic Programming