LeetCode 97 · Medium · 2-D Dynamic Programming

Interleaving String

Decide whether s3 can be built by weaving s1 and s2 together: every character of both used once, and each string's own order kept.

O(m·n)time
O(m·n)space
memo DFSon (i, j) · s3 index = i + j

lowercase letters a–z · s1 and s2: 0–6 characters · s3: 0–12 (any string may be empty)

s3 blue = taken from s1 · grey = taken from s2, along the current call path

dp cell (i, j) = can s1.substring(i) and s2.substring(j) weave into s3.substring(i + j) · ↓ take s1[i] · → take s2[j]

Call stack bottom → top

private String s1, s2, s3;private boolean[][] failed;public boolean isInterleave(String a, String b, String c) { if (a.length() + b.length() != c.length()) { return false; } s1 = a; s2 = b; s3 = c; failed = new boolean[a.length() + 1][b.length() + 1]; return dfs(0, 0);}private boolean dfs(int i, int j) { if (i == s1.length() && j == s2.length()) { return true; } if (failed[i][j]) { return false; } if (i < s1.length() && s1.charAt(i) == s3.charAt(i + j) && dfs(i + 1, j)) { return true; } if (j < s2.length() && s2.charAt(j) == s3.charAt(i + j) && dfs(i, j + 1)) { return true; } failed[i][j] = true; return false;}
i, j
—
s3[i + j]
—
memo entries
0
memo hits
0

Why it works

  1. Brute force decides, for each character of s3, whether it came from s1 or s2: up to 2m+n branches.
  2. Two numbers describe the state. After using i characters of s1 and j of s2, the next character of s3 is always s3[i + j]. Different branches that reach the same (i, j) face the same question, so a failed (i, j) is cached and never explored again.
  3. Complexity: (m+1)·(n+1) states, each tries at most two moves: O(m·n) time and space. Only false needs caching: a true returns all the way up at once.
  4. Pitfall: check s1.length() + s2.length() == s3.length() first. Without it, s3 could run out (StringIndexOutOfBoundsException) or have leftover characters that nobody checks.
  5. Bottom-up version: the same table filled from the bottom-right, dp[i][j] = (s1.charAt(i) == s3.charAt(i + j) && dp[i + 1][j]) || (s2.charAt(j) == s3.charAt(i + j) && dp[i][j + 1]). A greedy "take from whichever matches" fails when both match: in the "aab", "aac", "aacaab" preset, taking from s1 first hits a dead end.