Interleaving string
Shuffle two strings together the way you riffle two halves of a deck of cards: repeatedly take the next letter from the front of either string, as you like, until both are used up. The result is an interleaving of the two. Each string keeps its own letter order, but their letters can alternate in any pattern.
You get three strings, first, second and merged. Return True when some shuffle of first and second produces exactly merged, using every letter of both once and adding nothing, and False otherwise.
first = "dog", second = "cat", merged = "dcoagt"OutputTrueTake letters from "dog" and "cat" in turn: d, c, o, a, g, t.
first = "ab", second = "ac", merged = "acab"OutputTrueThe first a must come from "ac". Taking it from "ab" leaves "cab", whose c matches neither next letter (b or a).
first = "ab", second = "cd", merged = "bacd"OutputFalseThe b comes before the a, but "ab" needs its a first.
0 ≤ len(first), len(second) ≤ 100
0 ≤ len(merged) ≤ 200
All three strings use only lowercase English letters.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.