package main

func isInterleaveSlow(s1 string, s2 string, s3 string) bool {
	l := []int{len(s1), len(s2)} // Backtracking is rather slow...
	if l[0]+l[1] != len(s3) {
		return false
	}
	var st Stack = make([]int, 0)
	i := make([]int, 3)
	s := []string{s1, s2}
	for j := 0; i[2] < len(s3); {
		for ; j < 2; j++ {
			if i[j] < l[j] && s[j][i[j]] == s3[i[2]] {
				st.Push(j)
				i[j]++
				i[2], j = i[2]+1, 0
				break
			}
		}
		if j == 2 {
			if len(st) == 0 {
				return false
			}
			t := st.Pop().(int)
			i[t]--
			i[2], j = i[2]-1, t+1
		}
	}
	return true
}

func isInterleave(s1 string, s2 string, s3 string) bool {
	l1, l2, l3 := len(s1), len(s2), len(s3)
	switch {
	case l1+l2 != l3:
		return false
	case l1 == 0:
		return s2 == s3
	case l2 == 0:
		return s1 == s3
	}
	dp := make([][]bool, l1+1)
	for i := range dp {
		dp[i] = make([]bool, l2+1)
		if i == 0 {
			dp[0][0] = true
		} else {
			dp[i][0] = dp[i-1][0] && s1[i-1] == s3[i-1]
		}
	}
	for i := 1; i <= l2; i++ {
		if !dp[0][i-1] {
			break
		}
		dp[0][i] = s2[i-1] == s3[i-1]
	}
	for i1 := 1; i1 <= l1; i1++ {
		for i2 := 1; i2 <= l2; i2++ {
			dp[i1][i2] = (dp[i1-1][i2] && s1[i1-1] == s3[i1+i2-1]) ||
				(dp[i1][i2-1] && s2[i2-1] == s3[i1+i2-1])
		}
	}
	return dp[l1][l2]
}

// func main() {
// 	println(isInterleave("aabcc", "dbbca", "aadbbcbcac"), true)
// 	println(isInterleave("aabcc", "dbbca", "aadbbbaccc"), false)
// 	println(isInterleave("a", "b", "a"), false)
// }