The problem
Return true if s3 can be made by interleaving s1 and s2: taking all the characters of both and mixing them together, while each keeps its own order. aadbc interleaves abc and ad: a, a, d, b, c.
Examples
- Input
s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
- Output
true
- Input
s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
- Output
false
- Input
s1 = "", s2 = "", s3 = ""
- Output
true
Constraints
- 0 ≤ s1.length, s2.length ≤ 100
- 0 ≤ s3.length ≤ 200
- Only lowercase English letters.
The idea
The lengths must add up. Then let ok(i, j) say whether the first i letters of s1 and the first j of s2 can interleave into the first i + j letters of s3. The last of those letters came either from s1 — it must equal s1’s i-th letter, and ok(i − 1, j) must hold — or from s2, likewise with ok(i, j − 1).
Picture a grid where moving down takes a letter from s1 and moving right takes one from s2: the question is whether some path reaches the corner. One row at a time suffices.
- Time
- O(m · n)
- Space
- O(n)
Solution · every language run against every case
class Solution: def isInterleave(self, s1: str, s2: str, s3: str) -> bool: if len(s1) + len(s2) != len(s3): return False # ok[j] (in row i): can s1[:i] and s2[:j] interleave into s3[:i + j]? The last letter # of s3[:i + j] came from s1 or from s2. ok = [False] * (len(s2) + 1) for i in range(len(s1) + 1): for j in range(len(s2) + 1): if i == 0 and j == 0: ok[j] = True else: k = i + j - 1 from1 = i > 0 and ok[j] and s1[i - 1] == s3[k] # ok[j] still holds row i - 1 from2 = j > 0 and ok[j - 1] and s2[j - 1] == s3[k] ok[j] = from1 or from2 return ok[len(s2)]