97. Interleaving String
Given strings s1
, s2
, and s3
, find whether s3
is formed by an interleaving of s1
and s2
.
An interleaving of two strings s
and t
is a configuration where they are divided into non-empty substrings such that:
s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| <= 1
- The interleaving is
s1 + t1 + s2 + t2 + s3 + t3 + ...
ort1 + s1 + t2 + s2 + t3 + s3 + ...
Note: a + b
is the concatenation of strings a
and b
.
Example 1:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Example 2:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
Example 3:
Input: s1 = "", s2 = "", s3 = ""
Output: true
Constraints:
0 <= s1.length, s2.length <= 100
0 <= s3.length <= 200
s1
,s2
, ands3
consist of lower-case English letters.
# @lc code=start
using LeetCode
function is_interleave(s1::String, s2::String, s3::String)
len1, len2, len3 = length(s1), length(s2), length(s3)
len1 + len2 != len3 && return false
dp = OffsetArray(fill(false, len1 + 1, len2 + 1), -1, -1)
dp[0, 0] = true
for i in 0:len1, j in 0:len2
p = i + j
i > 0 && (dp[i, j] |= dp[i - 1, j] && s1[i] == s3[p])
j > 0 && (dp[i, j] |= dp[i, j - 1] && s2[j] == s3[p])
end
return dp[end, end]
end
# @lc code=end
is_interleave (generic function with 1 method)
This page was generated using DemoCards.jl and Literate.jl.