-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathinterleaving-string.py
55 lines (41 loc) · 1.42 KB
/
interleaving-string.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
from functools import lru_cache
class Solution:
# Memoized recursive approach
# Simplified
# TC: O(n * m) where n and m are the length of s1 and s2
# SC: O(n * m)
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
if len(s1) + len(s2) != len(s3):
return False
@lru_cache(None)
def dfs(n1, n2):
if n1 + n2 >= len(s3):
return True
s1_res, s2_res = False, False
if n1 < len(s1) and s1[n1] == s3[n1+n2]:
s1_res = dfs(n1+1, n2)
if s1_res:
return True
if n2 < len(s2) and s2[n2] == s3[n1+n2]:
s2_res = dfs(n1, n2+1)
return s2_res
return dfs(0, 0)
# Memoized recursive approach
# TC: O(n * m) where n and m are the length of s1 and s2
# SC: O(n * m)
def isInterleave2(self, s1: str, s2: str, s3: str) -> bool:
if len(s1) + len(s2) != len(s3):
return False
@lru_cache(None)
def dfs(n1, n2, n3):
if n3 >= len(s3):
return True
s1_res, s2_res = False, False
if n1 < len(s1) and s1[n1] == s3[n3]:
s1_res = dfs(n1+1, n2, n3+1)
if s1_res:
return True
if n2 < len(s2) and s2[n2] == s3[n3]:
s2_res = dfs(n1, n2+1, n3+1)
return s2_res
return dfs(0, 0, 0)