Blind Plus 100 Visualized

#97 · 2D DP

Interleaving String

Given strings s1, s2 and s3, decide whether s3 is formed by interleaving s1 and s2: merging them into one string while keeping the relative order of the characters inside each of s1 and s2.

MediumLeetCode
  • Computing
  • Depends on
  • Answer
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

2D boolean DP table over (letters used from s1, letters used from s2)

After taking i letters from s1 and j letters from s2, exactly i + j letters of s3 have been produced, so the pair (i, j) alone says where we are in s3. dp[i][j] is true if the remainders can still finish the job: the next letter s3[i + j] must equal s1[i] (then continue at (i + 1, j)) or s2[j] (then (i, j + 1)).

Memory layout

A (m + 1) × (n + 1) boolean array.

OperationCost
timeO(m · n)
spaceO(m · n), or O(min(m, n)) with a rolling row

Lattice-path view

The table is a grid path problem: start at (0, 0), each step moves down (consume s1) or right (consume s2) and is allowed only if the letter matches the next letter of s3; the question is whether some path reaches the opposite corner.

Memory layout

Implicit in the DP table.

OperationCost
path existenceO(m · n)

Why it fits

  • The position in s3 is determined by (i, j), so the state space is only (m + 1)(n + 1) even though the number of interleavings is exponential.
  • Each state has just two outgoing choices, so a DP over the grid decides reachability in one sweep.
  • Rows depend only on the next row, which makes a single rolling array possible.

Why alternatives degrade

Greedy (always take from s1 when letters match):
When both strings offer the same next letter the right choice may be only visible later; greedy fails on inputs like s1 = "aab", s2 = "aac".
Plain backtracking:
Exponential when many letters coincide (e.g., long runs of "a").
Sorting letters / counting characters:
Equal letter counts are necessary but not sufficient; order inside each string matters.

Four approaches, from naive to production

1 · beginner

Plain recursion

time O(2^(m+n)) worst casespace O(m + n)

rec(i, j): the next letter of s3 is s3[i + j]. If s1[i] matches, try consuming it; if that fails and s2[j] matches, try consuming that. Succeed when both strings are used up.

bool isInterleave(string s1, string s2, string s3) {
    if (s1.size() + s2.size() != s3.size()) return false;
    function<bool(int, int)> rec = [&](int i, int j) -> bool {
        if (i == (int)s1.size() && j == (int)s2.size()) return true;
        char c = s3[i + j];
        if (i < (int)s1.size() && s1[i] == c && rec(i + 1, j)) return true;
        if (j < (int)s2.size() && s2[j] == c && rec(i, j + 1)) return true;
        return false;
    };
    return rec(0, 0);
}

Flaws & bottlenecks

  • The same (i, j) pair can be reached by many interleaving prefixes and is re-explored.
  • Runs of equal letters make both branches viable at every step.
  • Recursion depth up to m + n.

Interviewer cross-questions

Why does (i, j) determine the position in s3?

Say: Exactly i + j letters have been produced, so the next one is s3[i + j].

Why check the lengths first?

Say: If |s1| + |s2| ≠ |s3| no interleaving exists, and the check prevents indexing past the end of s3.

How do you avoid re-exploring?

Say: Cache the result of each (i, j).

2 · intermediate

Memoised recursion

time O(m · n)space O(m · n)

Same recursion with a cache keyed by i · (n + 1) + j. A pair that already failed is rejected at once.

bool isInterleave(string s1, string s2, string s3) {
    if (s1.size() + s2.size() != s3.size()) return false;
    unordered_map<int, bool> memo;
    function<bool(int, int)> rec = [&](int i, int j) -> bool {
        if (i == (int)s1.size() && j == (int)s2.size()) return true;
        int key = i * ((int)s2.size() + 1) + j;
        auto it = memo.find(key);
        if (it != memo.end()) return it->second;
        char c = s3[i + j];
        bool ok = (i < (int)s1.size() && s1[i] == c && rec(i + 1, j)) || (j < (int)s2.size() && s2[j] == c && rec(i, j + 1));
        memo[key] = ok;
        return ok;
    };
    return rec(0, 0);
}

Flaws & bottlenecks

  • Recursion depth up to m + n.
  • Hash-map overhead.
  • Combines both branches into one expression, which hides which path succeeded.

Interviewer cross-questions

Why only cache failures?

Say: A success returns true all the way up immediately, so only failed pairs can be revisited; caching all results is simpler and equally correct.

What is the number of states?

Say: (m + 1)(n + 1), each evaluated in O(1) apart from its recursive calls.

How do you remove recursion?

Say: Fill the table bottom-up.

3 · advanced

Bottom-up table

time O(m · n)space O(m · n)

dp[m][n] = true. For i from m down to 0 and j from n down to 0: dp[i][j] = (s1[i] matches and dp[i + 1][j]) or (s2[j] matches and dp[i][j + 1]). The answer is dp[0][0].

bool isInterleave(string s1, string s2, string s3) {
    int m = s1.size(), n = s2.size();
    if (m + n != (int)s3.size()) return false;
    vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
    dp[m][n] = true;
    for (int i = m; i >= 0; i--) {
        for (int j = n; j >= 0; j--) {
            if (i == m && j == n) continue;
            char c = s3[i + j];
            dp[i][j] = (i < m && s1[i] == c && dp[i + 1][j]) || (j < n && s2[j] == c && dp[i][j + 1]);
        }
    }
    return dp[0][0];
}

Flaws & bottlenecks

  • Quadratic memory.
  • Computes cells that cannot be reached from (0, 0).
  • Easy to read s3 out of range if the length check is skipped.

Interviewer cross-questions

Which cells matter?

Say: Only those on lattice paths from (0, 0); a forward formulation visits exactly those and can stop early when a whole diagonal is false.

How would you also return the interleaving?

Say: Record the choice per cell and walk from (0, 0) following true cells.

Can the table shrink?

Say: Yes: each cell uses the cell below and to its right, so one row suffices.

4 · expert

Single rolling row

time O(m · n)space O(min(m, n))

Keep one boolean array of n + 1 slots. Updating row[j] in place uses the old value of the same slot as "the cell below" and the already-updated row[j + 1] as "the cell to the right". Swap so the row is the shorter string.

bool isInterleave(string s1, string s2, string s3) {
    if (s1.size() + s2.size() != s3.size()) return false;
    if (s1.size() < s2.size()) swap(s1, s2);
    int m = s1.size(), n = s2.size();
    vector<char> row(n + 1, 0);
    row[n] = 1;
    for (int i = m; i >= 0; i--) {
        for (int j = n; j >= 0; j--) {
            if (i == m && j == n) continue;
            char c = s3[i + j];
            row[j] = (i < m && s1[i] == c && row[j]) || (j < n && s2[j] == c && row[j + 1]);
        }
    }
    return row[0];
}

Flaws & bottlenecks

  • Cannot reconstruct the interleaving.
  • In-place update order matters: j must go downward so row[j + 1] is already new.
  • The aliasing of "old row[j]" is subtle for readers.

Interviewer cross-questions

Why does the loop over j go downward?

Say: row[j + 1] must already hold the CURRENT row's value (cell to the right), while row[j] still holds the previous row's value (cell below).

Is swapping s1 and s2 safe?

Say: Yes: interleaving is symmetric in the two inputs.

What are the edge cases?

Say: All three strings empty (true), one of s1 / s2 empty (then s3 must equal the other), differing total length (false), and many equal letters (the case that defeats backtracking).

Synchronized code walkthrough

Showing: Plain recursion — shares the player above; click any step to jump.

bool isInterleave(string s1, string s2, string s3) {
    if (s1.size() + s2.size() != s3.size()) return false;
    function<bool(int, int)> rec = [&](int i, int j) -> bool {
        if (i == (int)s1.size() && j == (int)s2.size()) return true;
        char c = s3[i + j];
        if (i < (int)s1.size() && s1[i] == c && rec(i + 1, j)) return true;
        if (j < (int)s2.size() && s2[j] == c && rec(i, j + 1)) return true;
        return false;
    };
    return rec(0, 0);
}