Interleaving String
Part of Practice: Prefix & Memo DP
Given strings s1, s2, and s3, decide whether s3 can be formed by interleaving s1 and s2: merging the two strings into one while keeping the characters of each in their original relative order. Every character of s1 and s2 must be used exactly once.
For example, "abc" and "xy" can interleave into "axbyc" but not into "axcyb" (the b and c swapped order).
Constraints: 0 <= s1.length, s2.length <= 100 and 0 <= s3.length <= 200.
Examples
- Input:
- s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
- Output:
- true
Take "aa" from s1, "dbbc" from s2, "bc" from s1, "a" from s2, "c" from s1.
- Input:
- s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
- Output:
- false
- Input:
- s1 = "", s2 = "", s3 = ""
- Output:
- true
Two empty strings interleave into the empty string.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.