Given strings s1, s2 and s3, return true if s3 can be formed by interleaving s1 and s2. Interleaving means splitting both strings into pieces and merging them while keeping the characters of each string in their original order.
- 0 <= s1.length, s2.length <= 100
- 0 <= s3.length <= 200
- All strings have lowercase English letters
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
A greedy "take from whichever string matches" fails when both strings offer the same character, and trying both choices blindly is exponential. Notice that the position in s3 is fixed once we know how much of s1 (i) and s2 (j) we used, so there are only (m+1)(n+1) situations. State: dp[i][j] is true if s1[:i] and s2[:j] interleave to s3[:i+j]. Recurrence: dp[i][j] is true if dp[i-1][j] and s1[i-1] == s3[i+j-1], or if dp[i][j-1] and s2[j-1] == s3[i+j-1]. Base case: dp[0][0] = true. One row of size n + 1 is enough.
Algorithm
- If
len(s1) + len(s2) != len(s3), return false. - Create
dpof sizen + 1for rowi = 0:dp[0] = trueanddp[j] = dp[j-1] and s2[j-1] == s3[j-1]. - For each
ifrom 1 tom:dp[0] = dp[0] and s1[i-1] == s3[i-1], then forjfrom 1:dp[j] = (dp[j] and s1[i-1] == s3[i+j-1]) or (dp[j-1] and s2[j-1] == s3[i+j-1]). - Return
dp[n].
O(m * n)Space: O(n)s1 = "a", s2 = "b", s3 = "abc" could return true from the table. In the 1D version, dp[j] before the update is the "from above" value.class Solution: def isInterleave(self, s1: str, s2: str, s3: str) -> bool: m, n = len(s1), len(s2) if m + n != len(s3): return False dp = [False] * (n + 1) dp[0] = True for j in range(1, n + 1): dp[j] = dp[j - 1] and s2[j - 1] == s3[j - 1] for i in range(1, m + 1): dp[0] = dp[0] and s1[i - 1] == s3[i - 1] for j in range(1, n + 1): c = s3[i + j - 1] # old dp[j] = from above (take s1[i-1]), dp[j-1] = from left (take s2[j-1]) dp[j] = (dp[j] and s1[i - 1] == c) or (dp[j - 1] and s2[j - 1] == c) return dp[n]