0097.交错字符串

https://leetcode.cn/problems/interleaving-string/

方法一：动态规划

时间复杂度 $O(m \times n)$，空间复杂度 $O(m \times n)$。

func isInterleave(s1 string, s2 string, s3 string) bool {
	m, n, l, dp := len(s1), len(s2), len(s3), make([][]bool, len(s1)+1)
	for i := 0; i <= m; i++ {
		dp[i] = make([]bool, n+1)
	}
	dp[0][0] = true
	if m+n != l {
		return false
	}
	for i := 0; i <= m; i++ {
		for j := 0; j <= n; j++ {
			k := i + j - 1
			if i > 0 {
				dp[i][j] = dp[i-1][j] && s1[i-1] == s3[k]
			}
			if j > 0 {
				dp[i][j] = dp[i][j] || (dp[i][j-1] && s2[j-1] == s3[k])
			}
		}
	}
	return dp[m][n]
}