Interleaving String
Medium · 2-D Dynamic Programming
You are given three strings. Determine whether the third string can be formed by interleaving the characters of the first two strings, preserving the relative order of characters from each source string but allowing them to be mixed together in any pattern. Return true if such an interleaving exists, otherwise return false.
Examples
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Why: You can pick letters from s1 and s2 in order, weaving them together, to reproduce s3 exactly.Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
Why: No way of interleaving the two source strings while keeping their internal order reproduces this target.Input: s1 = "", s2 = "", s3 = ""
Output: true
Why: Two empty strings trivially interleave into an empty result.Constraints
0 <= s1.length, s2.length <= 100, 0 <= s3.length <= 200, all strings consist of lowercase English letters
Practise it by voice
Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.
This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Interleaving String. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.