97. Interleaving String 交织字符串

题目

给定一个字符串 s1, s2, s3, 查找并判断 s3 是否由 s1 和 s2 交叉组织而成。

解析

我们可以将 s1 和 s2 的所有交叉情况看作一颗二叉树，则从根节点到每个叶子节点的路径就是一种交叉情况。要判断 s3 是否是由 s1 和 s2 交叉而成，就是判断是否有一条路径和 s3 恰好相等。
这个二叉树的性质是，如果一个节点是父节点的左节点，则该节点来自 s1，如果一个节点是父节点的右节点，则该节点来自 s2。
搜索策略

1. 每次遇到左右均可的情况时，我们优先搜索左节点，并且将右节点压栈
2. 当一个搜索左右均不满足时，从栈中弹出一个节点，然后继续搜索，若无可弹出的节点，说明 s3 不能被 s1 s2 组成。
   所以需要一个栈，栈存储的数据是 s1 的位置 m 和 s2 的位置 n

伪代码

for i<len(s3)
  if s2[n] == s3[i]
    stack.push(m,n)
  if s1[m] == s3[i]
    i++,m++
    continue
  if stack is nil
    return false
  m,n = stack.pop
  i=m+n+2

代码

func isInterleave(s1 string, s2 string, s3 string) bool {
    stack := make([][2]int, 100)
    si := 0
    m:=0
    n:=0
    i:=0
    for i<len(s3) {
        if n < len(s2) && s3[i] == s2[n] {
            stack[si] = [2]int{m,n}
            si++
        }
        if m < len(s1) && s3[i] == s1[m] {
            i++
            m++
            continue
        }
        if si == 0 {
            return false
        }
        m,n = stack[si-1][0], stack[si-1][1]
        si--
        n++
        i=m+n
    }
    return m == len(s1) && n == len(s2)
}

超时了，这个算法看起来像是暴力搜索。
最后结束循环的条件是 i<len(s3)。只有当 m == len(s1) 并且 n == len(s2) 时，说明全部匹配完毕。