題目在此 97. Interleaving String
給定三個字串 s1、s2、s3，請問 s3 是否可以由 s1 與 s2 交錯組成？
解題思維
名詞解說：
這題以標準解法來說，就是 DFS + memoization。
那 memoization 有人會自己實作 DP 或是直接用 @cache，這邊我們就用 @cache 來實作。![image 106]()
在這裡簡單解釋一下 @cache, @lru_cache 的用法，這個 decorator 會幫你把函式的輸入與輸出記錄下來，如果下次輸入的參數與之前的一樣，就直接回傳之前的結果，不會再執行一次函式。
如果想了解更多細節，可以參考官方文件 functools.cache。
關於這題，我是想像成 2D 的地圖，Y 軸是 s1，X 軸是 s2，然後從左上角開始走，如果可以走到右下角，那就代表可以組成 s3。
途中跟 s3 確認是否含有 s1 or s2，如果發現走不下去了，就回傳 False。
![image 106]()
程式碼
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
| class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
if (size1 := len(s1)) + (size2 := len(s2)) != (size3 := len(s3)):
return False
if size1 == size2 == 0:
return True
@cache
def dfs(index1, index2):
if index1 == size1 and index2 == size2:
return True
index3 = index1 + index2
result1 = result2 = False
if index1 < size1 and s1[index1] == s3[index3]:
result1 = dfs(index1 + 1, index2)
if not result1 and index2 < size2 and s2[index2] == s3[index3]:
result2 = dfs(index1, index2 + 1)
return result1 or result2
return dfs(0, 0)
|
![image 106]()
也許你也會想看看
