Dynamic Programming - 97. Interleaving String

97. Interleaving String

Given s1s2s3, find whether s3 is formed by the interleaving of s1 and s2.

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false

``````(  )s1 0 d b b c a
s2
0      T F F F F F
a      T F F F F F
a      T T T T T F
b      F T T F T F
c      F F T T T T
c      F F F T F T
``````

go：

``````func isInterleave(s1 string, s2 string, s3 string) bool {
if len(s1) + len(s2) != len(s3) {
return false
}

m, n := len(s2), len(s1)
dp := make([][]bool, m+1)
for i := 0; i < m + 1; i++ {
dp[i] = make([]bool, n+1)
}

for i := 0; i < m+1; i++ {
for j := 0; j < n+1; j++ {
if i == 0 && j != 0 {
dp[i][j] = dp[i][j-1] && (s1[j-1] == s3[j-1])
} else if i != 0 && j == 0 {
dp[i][j] = dp[i-1][j] && (s2[i-1] == s3[i-1])
} else if i == 0 && j == 0 {
dp[i][j] = true
} else {
dp[i][j] = ((dp[i-1][j] && s2[i-1] == s3[i+j-1]) || (dp[i][j-1] && s1[j-1] == s3[i+j-1]))
}
}

}

return dp[m][n]
}
``````

Nothing just happens, it's all part of a plan.