Interleave Two Strings
Problem
A log merger combines two event streams into one without reordering either stream. Given strings a, b and c, return True if c can be formed by interleaving a and b: every character of a and of b is used exactly once, and the characters of a appear in c in their original order, as do the characters of b. a and b have up to 100 characters each, and c up to 200.
Examples
Input: a = "aabcc", b = "dbbca", c = "aadbbcbcac"
Output: True
Why: aa from a, dbbc from b, bc from a, a from b, c from aInput: a = "aabcc", b = "dbbca", c = "aadbbbaccc"
Output: FalseInput: a = "", b = "", c = ""
Output: True
Why: edge case, two empty streams merge into an empty oneHints
0 / 3
Greedily taking the next character from whichever stream matches fails when both match. You would need to try both, and that branching repeats work.
The state is how many characters of a and of b have been used, i and j. Then c[i + j - 1] must have come from a[i - 1] or from b[j - 1], just like the edit distance table looks at the cell above and the cell to the left.
Let ok[i][j] mean the first i of a and first j of b interleave into the first i + j of c. ok[i][j] is true if (ok[i - 1][j] and a[i - 1] == c[i + j - 1]) or (ok[i][j - 1] and b[j - 1] == c[i + j - 1]). Check the lengths first.
Solution
If the lengths do not add up, the answer is False at once. Otherwise the problem is a two-string table in the style of edit distance: cell (i, j) records whether the first i characters of a and the first j of b can produce the first i + j characters of c. The last character of that prefix came either from a, which needs cell (i - 1, j) to be true and the characters to match, or from b, which needs cell (i, j - 1). Each row only reads the row above and the cell to its left, so a single row updated in place is enough. Time is O(len(a) · len(b)), and space is O(len(b)).
def is_interleaving(a, b, c):
if len(a) + len(b) != len(c):
return False
ok = [True] + [False] * len(b) # row i = 0: only b used so far
for j in range(1, len(b) + 1):
ok[j] = ok[j - 1] and b[j - 1] == c[j - 1]
for i in range(1, len(a) + 1):
ok[0] = ok[0] and a[i - 1] == c[i - 1]
for j in range(1, len(b) + 1):
ch = c[i + j - 1]
from_a = ok[j] and a[i - 1] == ch # ok[j] still holds the row above
from_b = ok[j - 1] and b[j - 1] == ch # ok[j - 1] is this row already
ok[j] = from_a or from_b
return ok[len(b)]
print(is_interleaving("aabcc", "dbbca", "aadbbcbcac")) # -> True
print(is_interleaving("aabcc", "dbbca", "aadbbbaccc")) # -> False
print(is_interleaving("", "", "")) # -> TrueStuck on the idea rather than the code? Edit Distance covers it.