2021-06-19：交错字符串。 有三个字符串s1,s2,s3。判断s3是否由s1和s2交错组成的。比如s1=“abc“,s2

package main

import "fmt"

func main() {
    s1 := "aaabsk"
    s2 := "aacfk"
    s3 := "aaacaabfskk"
    ret := isInterleave(s1, s2, s3)
    fmt.Println(ret)
}

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