0097. Interleaving String | LeetCode Cookbook

[halfrost]

https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0097.Interleaving-String/

[hanlins]

这道题可以用分治动规:

func isInterleave(s1 string, s2 string, 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 k := 1; k <= len(s3); k++ {
        for i := 0; i <= len(s1) && i <= k; i++ {
            j := k - i
            if j > len(s2) {continue}
            if (i > 0 && s1[i-1] == s3[k-1] && dp[i-1][j]) ||
               (j > 0 && s2[j-1] == s3[k-1] && dp[i][j-1]) {
                dp[i][j] = true
            }
        }
    }

    return dp[len(s1)][len(s2)]
}