We’re preparing your current view and syncing the latest data.
Given three strings s1, s2, and s3, determine 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 and t = t1 + t2 + ... + tm, and s3 = s1 + t1 + s2 + t2 + ... or t1 + s1 + t2 + s2 + ..., maintaining the left-to-right order of characters from s1 and s2.
The input consists of three strings s1, s2, and s3.
Return true if s3 is formed by an interleaving of s1 and s2, otherwise false.
1 <= s1.length, s2.length <= 100 0 <= s3.length <= 200 s1, s2, and s3 consist of lowercase English letters.
Example 1
Input
s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output
true
Explanation
s3 can be formed by interleaving s1 and s2: a a d b b c b c a c.
Example 2
Input
s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output
false
Explanation
s3 cannot be formed by any interleaving of s1 and s2.