164. Interleaving String

Hard · Dynamic Programming

An interleaving of two strings is formed by merging them together while preserving the relative order of characters within each original string. For example, "aXbY" is an interleaving of "ab" and "XY".

Given three strings s1, s2, and s3 (provided as input = [s1, s2, s3]), determine whether s3 is an interleaving of s1 and s2. Return true if it is, false otherwise.

You must use each character from s1 and s2 exactly once, in their original order, but you can choose which string to take the next character from at each step.

Examples

Example 1
Input: ["aabcc","dbbca","aadbbcbcac"]
Output: true
Explanation: Interleaving exists
Example 2
Input: ["aabcc","dbbca","aadbbbaccc"]
Output: false
Explanation: No valid interleaving

Constraints