267. Interleaving String

Given strings s1, s2, and s3, return true if s3 is formed by an interleaving of s1 and s2 (preserving the left-to-right order of each). Input: '"s1", "s2", "s3"'.

Input: '"s1", "s2", "s3"'.

Output: Boolean — true or false.

Examples

Input: "aabcc", "dbbca", "aadbbcbcac"
Output: true
Explanation: Valid interleaving.

Input: "aabcc", "dbbca", "aadbbbaccc"
Output: false
Explanation: Cannot interleave.

Input: "", "", ""
Output: true
Explanation: All empty.

Constraints

• 0<=s1.length,s2.length<=100
• 0<=s3.length<=200

Asked by