All problems

Interleaving Strings

Medium · dynamic programming

You are given three strings s1, s2 and s3.

Say that s3 is an interleaving of s1 and s2 if it can be built like this. Start with an empty result and repeat the following until both s1 and s2 are used up: take the next unused character from the front of s1 or the next unused character from the front of s2 (your choice each time) and append it to the result. Each string's characters are therefore used in their original order, and every character of both strings is used exactly once.

Return true if s3 can be built this way, and false otherwise. Either of s1 and s2 may be empty, and s3 is never an interleaving if its length differs from the combined length of the other two.

Examples

Example 1

Input: s1 = "ab", s2 = "cd", s3 = "acbd"

Output: true

Take "a" from s1, "c" from s2, "b" from s1, then "d" from s2.

Example 2

Input: s1 = "ab", s2 = "cd", s3 = "adbc"

Output: false

After "a", the next characters available are "b" and "c", never "d", because "d" comes after "c" in s2.

Example 3

Input: s1 = "", s2 = "xyz", s3 = "xyz"

Output: true

With s1 empty, every character has to come from s2, in order.

Constraints

• 0 <= len(s1), len(s2) <= 100
• 0 <= len(s3) <= 200
• s1, s2 and s3 contain only lowercase English letters.