150NeetCode 150

116.Interleaving String

Medium2-D Dynamic Programming · 6/11
LeetCode #97Video

Problem

Given strings s1, s2 and s3, determine whether s3 is formed by an interleaving of s1 and s2.

An interleaving splits s1 and s2 into pieces and merges them alternately while keeping the characters of each string in their original order. Equivalently: can you read s3 left to right, assigning each character to either s1 or s2, so that the characters assigned to s1 spell s1 and those assigned to s2 spell s2?

Examples

Input:  s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Explanation: "aa" + "dbbc" + "bc" + "a" + "c"  →  s1 gives aa|bc|c, s2 gives dbbc|a.
Input:  s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
Input:  s1 = "", s2 = "", s3 = ""
Output: true

Constraints

  • 0 <= s1.length, s2.length <= 100
  • 0 <= s3.length <= 200
  • s1, s2, s3 consist of lowercase English letters.

💡 Key Insight

If we have used i characters of s1 and j of s2, the next character of s3 is forced to be s3[i + j] — so the state is just (i, j). From there, we can advance in s1 if s1[i] == s3[i + j], or in s2 if s2[j] == s3[i + j]. Greedy fails when both match, so we need DP over the (m+1) x (n+1) grid, which compresses to one row. Always check m + n == s3.length() first.

Recursion (Brute Force)

TimeO(2^(m+n))SpaceO(m + n)

Intuition

dfs(i, j) answers: can s3[i+j..] be formed from s1[i..] and s2[j..]? Try taking the next character from s1 and, if that fails, from s2.

Algorithm

  1. If m + n != s3.length(), return false.
  2. dfs(i, j):
    • If i == m and j == n, return true.
    • k = i + j.
    • If i < m and s1[i] == s3[k] and dfs(i + 1, j), return true.
    • If j < n and s2[j] == s3[k] and dfs(i, j + 1), return true.
    • Return false.

Visualization

flowchart TD
    A["dfs(0,0)<br/>s1='ab' s2='ac' s3='acab'"] -->|"s1 'a'"| B["dfs(1,0)<br/>need 'c'"]
    A -->|"s2 'a'"| C["dfs(0,1)<br/>need 'c'"]
    B -->|"s1 'b' != 'c'"| D["fail"]
    B -->|"s2 'a' != 'c'"| E["fail"]
    C -->|"s2 'c'"| F["dfs(0,2)<br/>need 'a'"]
    F -->|"s1 'a'"| G["dfs(1,2)<br/>need 'b'"]
    G -->|"s1 'b'"| H["dfs(2,2) = true"]

Both strings start with 'a', so a greedy choice (always take from s1) would fail; we must explore both branches.

Code

java
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) {
            return false;
        }
        return dfs(s1, s2, s3, 0, 0);
    }

    private boolean dfs(String s1, String s2, String s3, int i, int j) {
        if (i == s1.length() && j == s2.length()) {
            return true; // consumed everything
        }
        int k = i + j; // next char of s3 to match
        if (i < s1.length() && s1.charAt(i) == s3.charAt(k) && dfs(s1, s2, s3, i + 1, j)) {
            return true;
        }
        return j < s2.length() && s2.charAt(j) == s3.charAt(k) && dfs(s1, s2, s3, i, j + 1);
    }
}

Complexity

  • Time: O(2^(m+n)) — two branches at each of up to m + n steps.
  • Space: O(m + n) — recursion depth.

Complexity Comparison

Approach Time Space
Recursion (Brute Force) O(2^(m+n)) O(m + n)
Top-Down Memoization O(m · n) O(m · n)
Bottom-Up 2-D Tabulation O(m · n) O(m · n)
Space-Optimized 1-D DP O(m · n) O(n)

Common Pitfalls

  • Skipping the m + n == s3.length() check — the DP can then read past the end of s3 or return true for a too-long s3.
  • Greedy two-pointer matching: when s1[i] and s2[j] both equal s3[k], you cannot know which to take without exploring both.
  • Using a third index k as part of the state — it is always i + j, so a 3-D table is wasted memory.
  • In the 1-D version, forgetting that dp[j] must be recomputed for j = 0 on every row (it may turn false).
  • Empty strings: s1 = "" reduces to s2 == s3; make sure your bounds checks allow m = 0 or n = 0.