Interleaving String

Medium#97two strings

You get three strings a, b and c. Find out whether c can be woven from a and b: every letter of both used exactly once, each string's letters kept in their order, a's and b's letters mixed in any way. Our example: "acab" from "ab" and "ac" — true: a and c from "ac", then a and b from "ab".

97 Interleaving StringWalkthrough · 1×

Example: a = "ab", b = "ac", c = "acab". Both a and b start with a, so c's first letter could come from either; only one choice works.

acabc0a1c2a3b
true: can be builtfalse: cannotthis step, its letterscomes from herethe weave behind the answer

2 + 2 = 4 = len(c): the lengths fit, every letter of a and b must be used once

01/24
restart · back · play · step
Speed
1function isInterleave(a, b, c):
2 if len(a) + len(b) != len(c): return false
3 dp = table of len(a) + 1 by len(b) + 1, all false
4 dp[0][0] = true
5 for i from 0 to len(a):
6 for j from 0 to len(b):
7 if i > 0 and dp[i - 1][j]
8 and a[i - 1] == c[i + j - 1]:
9 dp[i][j] = true // the last letter from a
10 if j > 0 and dp[i][j - 1]
11 and b[j - 1] == c[i + j - 1]:
12 dp[i][j] = true // the last letter from b
13 return dp[len(a)][len(b)]
state
dp
–
i
–
j
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. The last letter of a weave of i letters of a and j letters of b is a[i - 1] or b[j - 1]. So (i, j) can be built exactly when (i - 1, j) can and a[i - 1] is that letter of c, or (i, j - 1) can and b[j - 1] is.
  2. The table keeps every way at once. Taking c’s first a from a looks fine, but (1, 1) is false: c then needs c, and neither string offers it. The other choice, (0, 1), carries on to the end.
  3. Each cell reads only the cell above and the one to the left, both already filled in row-by-row order, so the bottom-right cell answers for the whole strings.

Complexity

Time O(n × m) for a and b of lengths n and m: one cell per pair of prefixes, each checked in constant time. Memory O(n × m) for the table; one row updated in place is enough, O(m).

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.