DSA · Dynamic Programming · #88
Interleaving String
Module 47 · difficulty 3/5·⏱ 30:00starts on first keystroke
Given strings `s1`, `s2`, and `s3`, return `true` if `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 split into substrings such that: - `s = s_1 + s_2 + ... + s_n` - `t = t_1 + t_2 + ... + t_m` - `|n - m| <= 1` - The interleaving is `s_1 + t_1 + s_2 + t_2 + ...` or `t_1 + s_1 + t_2 + s_2 + ...` The relative order of characters within `s1` and within `s2` must be preserved. Implement `isInterleave(s1, s2, s3)` returning a boolean.
Examples
s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"→true— One valid interleaving: a a (s1) d b b (s2) c (s1) b c (s2) a c (mixed) preserving order.s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"→false— No way to interleave s1 and s2 to produce s3.s1 = "", s2 = "", s3 = ""→true— Two empty strings interleave to the empty string.
Constraints
- · 0 <= s1.length, s2.length <= 100
- · 0 <= s3.length <= 200
- · s1, s2, and s3 consist of lowercase English letters.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.