Interleaving Strings

Shuffle two strings together like the two halves of a deck of cards: take characters from the front of a or from the front of b, one at a time, in any pattern, until both are used up. The characters of each string keep their own order. For example, "abc" and "xy" can make "axbyc", "xyabc" or "abxcy", but not "bacxy".

Write is_interleaving(a, b, c) that returns True if c can be made this way from a and b, and False otherwise.

Examples

is_interleaving("dog", "cat", "dcoagt")  # returns True
is_interleaving("ab", "ab", "abba")      # returns False
is_interleaving("abc", "", "abc")        # returns True

Constraints

• 0 <= len(a), len(b) <= 250
• 0 <= len(c) <= 600
• All three strings hold lowercase letters only.