loading

Interleaving String — Step-by-Step Visualization

mediumLeetCode #97StringDynamic Programming

Given strings `s1`, `s2`, and `s3`, find whether `s3` is formed by an interleaving of `s1` and `s2`. An interleaving of two strings `s` and `t` is a configuration where they are divided into non-empty substrings such that `s3` is formed by joining them in order.

Algorithm Pattern

2D Dynamic Programming

Key Idea

We use a 2D boolean array `dp[i][j]` to represent whether `s3[0...i+j-1]` can be formed by interleaving `s1[0...i-1]` and `s2[0...j-1]`. To calculate `dp[i][j]`, we check if the current character `s3[i+j-1]` matches `s1[i-1]` (and `dp[i-1][j]` was true) OR if it matches `s2[j-1]` (and `dp[i][j-1]` was true).

Step-by-Step Approach

  1. If `len(s1) + len(s2) != len(s3)`, return `False` immediately.
  2. Initialize `dp` table of size `(m+1) x (n+1)` with `False`.
  3. Base Case: `dp[0][0] = True` (two empty strings form an empty string).
  4. Fill the first row and first column for cases where only one string is used.
  5. Iterate through the rest of the table: `dp[i][j]` is true if (`s1[i-1] == s3[i+j-1]` and `dp[i-1][j]`) or (`s2[j-1] == s3[i+j-1]` and `dp[i][j-1]`).

Common Gotchas

  • The length check is a vital first step.
  • The table size is `(len1+1) * (len2+1)` because we need to account for the empty string prefixes.

Related Problems

← All problems