97-interleaving-string¶
Try it on leetcode
Description¶
Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.
An interleaving of two strings s and t is a configuration where they are divided into non-empty substrings such that:
s = s1 + s2 + ... + snt = t1 + t2 + ... + tm|n - m| <= 1- The interleaving is
s1 + t1 + s2 + t2 + s3 + t3 + ...ort1 + s1 + t2 + s2 + t3 + s3 + ...
Note: a + b is the concatenation of strings a and b.
Example 1:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" Output: true
Example 2:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" Output: false
Example 3:
Input: s1 = "", s2 = "", s3 = "" Output: true
Constraints:
0 <= s1.length, s2.length <= 1000 <= s3.length <= 200s1,s2, ands3consist of lowercase English letters.
Follow up: Could you solve it using only O(s2.length) additional memory space?
Solution(Python)¶
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
return self.memoize(s1, s2, s3)
# Time Complexity: O(2^(m+n))
# space Complexity: O(m+n)
def bruteforce(self, s1: str, s2: str, s3: str) -> bool:
def dfs(s1,i,s2,j,res,s3):
if res == s3 and i == len(s1) and j == len(s2):
return True
ans = False
if i < len(s1):
ans |= dfs(s1,i+1,s2,j,res+s1[i],s3)
if j < len(s2):
ans |= dfs(s1,i,s2,j+1,res+s2[j],s3)
return ans
if len(s1) + len(s2) != len(s3):
return False
return dfs(s1,0,s2,0,"",s3)
# Time Complexity: O(m*n)
# space Complexity: O(m*n)
def memoize(self, s1: str, s2: str, s3: str) -> bool:
if len(s1) + len(s2) != len(s3):
return False
dp = [[0 for _ in range(len(s2)+1)]for _ in range(len(s1)+1)]
for i in range(len(s1)+1):
for j in range(len(s2)+1):
if i == 0 and j == 0:
dp[i][j] = True
elif i == 0:
dp[i][j] = dp[i][j-1] and s2[j-1] == s3[i+j-1]
elif j == 0:
dp[i][j] = dp[i-1][j] and s1[i-1] == s3[i+j-1]
else:
dp[i][j] = ( dp[i][j-1] and s2[j-1] == s3[i+j-1] ) or (dp[i-1][j] and s1[i-1] == s3[i+j-1] )
return dp[-1][-1]