DSA problem
Interleaving String
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 s and t are divided into n and m substrings respectively, such that:
s = s_1 + s_2 + ... + s_n and t = t_1 + t_2 + ... + t_m with |n - m| <= 1, and the interleaving is s_1 + t_1 + s_2 + t_2 + ... or t_1 + s_1 + t_2 + s_2 + .... Equivalently, the characters of s1 and s2 keep their relative order inside s3, and together they make up exactly s3.
A naive recursion tries every position in s3 and picks the next character from either s1 or s2, giving O(2^(m+n)) time. Memoization on (i, j) — the number of characters consumed from each source — drops it to polynomial time, because once i and j are fixed, the position in s3 is determined as i + j.
The optimal approach uses a 2D DP. Define dp[i][j] as a boolean meaning "the prefix s3[0..i+j) is an interleaving of s1[0..i) and s2[0..j)". The recurrence is:
dp[i][j] = (dp[i-1][j] && s1[i-1] == s3[i+j-1]) || (dp[i][j-1] && s2[j-1] == s3[i+j-1]). Initialize dp[0][0] = true, fill the first row and column by simple string-prefix matching, then sweep the table. This runs in O(m * n) time and O(m * n) space, easily compressible to O(min(m, n)).
Examples
s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"trues1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"falses1 = "", s2 = "", s3 = ""trueConstraints
- 0 <= s1.length, s2.length <= 100
- 0 <= s3.length <= 200
- s1, s2, and s3 consist of lowercase English letters.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.