LeetCode 筆記 - 97. Interleaving String

Posted on

題目在此 97. Interleaving String

給定三個字串 s1、s2、s3，請問 s3 是否可以由 s1 與 s2 交錯組成？

解題思維

名詞解說：

  • Depth First Search
  • Dynamic programming

這題以標準解法來說，就是 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

也許你也會想看看