Interleaving String
Medium · Dynamic Programming · String · Dynamic Programming
Problem
Given strings s1, s2 and s3, decide whether s3 is an interleaving of s1 and s2.
s3 is an interleaving when it can be built by taking the characters of s1 and s2 one at a time, each time from either string, so that every character of both strings is used exactly once and each string's characters keep their original order. In other words, the positions of s3 can be split into two groups that spell s1 and s2.
Return true if s3 is an interleaving of s1 and s2, otherwise false.
Examples
Input: s1 = "ab", s2 = "cd", s3 = "acbd" Output: true
Take a from s1, c from s2, b from s1, d from s2.
Input: s1 = "ab", s2 = "cd", s3 = "abdc" Output: false
d would have to be taken before c, which breaks the order of s2.
Input: s1 = "ab", s2 = "ac", s3 = "acab" Output: true
At the first a both strings match. Taking it from s1 leaves b needed before c, which fails; taking it from s2 leaves c from s2, then a, b from s1.
Constraints
- 0 <= s1.length, s2.length <= 100
- 0 <= s3.length <= 200
- All strings consist of lowercase English letters
Approaches
- Try both choices recursively — time O(2^(m+n)) in the worst case, space O(m + n) for the call stack
Follow-up
To count the interleavings instead of testing for one, replace or with +: ways[i][j] = ways[i-1][j] (if s1 matches) + ways[i][j-1] (if s2 matches). With three strings the state becomes (i, j, k) and the table three-dimensional.
Related problems
Start free on Cariara · Coding problems · System design studio
