Interleaving String

Given 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 s and t are divided into n and m substrings respectively, such that:

• s = s1 + s2 + ... + sn
• t = t1 + t2 + ... + tm
• |n - m| <= 1
• The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ...

In other words, s3 is formed by merging s1 and s2 while preserving the relative order of characters within each string.

---

Example 1

s1 = "aabcc"
s2 = "dbbca"

s3 = "aadbbcbcac"  ->  True
     a a d b b c b c a c
     ^ ^     ^ ^ ^   ^ ^   <- from s1: "aabcc"
         ^ ^       ^       <- from s2: "dbbca"

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: True
Explanation: s3 can be formed by interleaving s1 and s2 while preserving their character orders.

Example 2

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: False
Explanation: No valid interleaving of s1 and s2 produces s3.

---

Constraints

• 0 <= s1.length, s2.length <= 100
• 0 <= s3.length <= 200
• s1, s2, and s3 consist of lowercase English letters