Interleaving string

Hard TimeO(n·m) SpaceO(n·m)

Interleaving two strings means taking characters from each in turn, in any pattern, keeping the order within each of them and using both up entirely. Given a, b and c, say whether c is an interleaving of a and b. The length of c must equal the other two combined.

Examples

Example 1

Input
a = "ab"b = "cd"c = "acbd"
Output
true
a, c, b, d — ab stays in order, cd stays in order, and both are used up.

Example 2

Input
a = "ab"b = "cd"c = "abcde"
Output
false
"abcde" is five characters and "ab" with "cd" is only four.

The Code

function isInterleave(a, b, c) {
  if (a.length + b.length !== c.length) return false;
  const dp = [];
  for (let i = 0; i <= a.length; i++) {
    dp.push(new Array(b.length + 1).fill(false));
  }
  dp[0][0] = true;
  for (let i = 0; i <= a.length; i++) {
    for (let j = 0; j <= b.length; j++) {
      if (i > 0 && dp[i - 1][j] && a[i - 1] === c[i + j - 1]) dp[i][j] = true;
      if (j > 0 && dp[i][j - 1] && b[j - 1] === c[i + j - 1]) dp[i][j] = true;
    }
  }
  return dp[a.length][b.length];
}
isInterleave("ab", "cd", "acbd");
Done

The first 19 calls, of 21. This one does not fit on a page.

Step through isInterleave("ab", "cd", "acbd") call by call

More like this

All dynamic programming examples (20) →