139. Word Break

──────────────────────────────────────────────────────────────────────

139. Word Break

給一個字串 s 和一個單字陣列 wordDict，問能不能用字典裡的單字（每個都可以重複使用）剛好拼出整個 s。

思路

這個題目的要求是給定一個字串與一個陣列，陣列裡面裡面有多個單字，目標是要回答，是否可以透過任意組合陣列裡面的單字，且陣列裡面的每個單字都是可以重複使用，可以拼湊出題目給的字串。

題目的要求很清楚，直覺的解法也是可以透過暴力解的方式來處理。但是暴力解的方式需要注意要確定方向，因為陣列裡面的單字可以重複使用，所以不能夠過無限窮舉出所有的單字的排列組合，再來確定組合中是否有目標。

因此暴力解的方向在於要怎麼從目標的字串漸漸的把所有的組合都給找完，排列的方式也很直覺，可以想像用拼圖的方式，把陣列中的每個單字當作一片拼圖，嘗試著把拼圖拼上去，如果能夠把拼圖拼完，就代表著可以找到目標。

但是這個題目沒有明講，但是會造成拼圖邏輯出問題的地方在於，有接單字可能會特別的長，他雖然一次可以覆蓋掉很多字元，但是其他的拼圖也就拼不上去了，例如：

s = "abcde"
words = ["abcd", "abc", "de"]

當使用第一個單字 abcd 當作拼圖的時候，一下就可以蓋掉四個字元，但是剩下的拼圖中，沒有任何一個 e 可以拼完剩下的拼圖，這樣的話雖然 abcd 可以使用，但是是屬於沒有作用的拼圖。

這個題目的狀態轉移其實滿自由的，最主要是如果在目標字串中，前面 i 個位置的字元都已經檢查過了，只需要繼續檢查後面的字元就可以了，所以狀態轉移方程可以是傳遞檢查的位置 i 或是剩餘還沒檢查過的 s[i:] 字串。

$d p (i) = \exists w o r d \in w o r d D i c t : s [i : i + l e n (w o r d)] = w o r d \land d p (i + l e n (w o r d))$

也就是只要有一個單字對得上、而且剩下的部分也拼得完，dp(i) 就是 True。

解題方向

遞迴

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:

        def dfs(i):
            # TODO: 終止條件
            # 選擇
            for word in wordDict:
                # word 比剩餘要檢查的字串還長
                if len(s) - i < len(word):
                    continue
                # word 無法拼入拼圖
                if not s[i:].startswith(word):
                    continue
                # 剩餘的字串如果拼得完，就不必再試其他單字
                if dfs(i + len(word)):
                    return True
            return False
        
        return dfs(0)

上述的方式是比較適合閱讀，但是比較合適的寫法可以這樣改寫

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        
        def dfs(i):
            # TODO: 終止條件
            for word in wordDict:
                # 剩餘的字串長度比當前要檢查的單字還長
                if len(s) - i >= len(word):
                    # 又剛好符合最前面的字元
                    if s[i:].startswith(word):
                        # 當繼續拼圖下去可以拼完所有的拼圖
                        if dfs(i + len(word)):
                            return True
            return False
        
        return dfs(0)

但是這樣並沒有終止條件，終止條件應該是當指針已經掃瞄完畢目標字串的所有字元時，代表已經拼完拼圖了。最後一個小優化是，題目給訂的陣列，可能存在著重複的單字，但是既然單字是可以重複使用的，而我們並不需要知道每個單字是否重複出現，可以在最一開始的時候就只使用不重複的單字。

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        
        wordDict = set(wordDict)

        def dfs(i):
            if i == len(s):
                return True
            for word in wordDict:
                if len(s) - i >= len(word):
                    if s[i:].startswith(word):
                        if dfs(i + len(word)):
                            return True
            return False
        
        return dfs(0)

以下是上述所使用的利用剩餘的字串來做狀態轉移的方式。

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        wordDict = set(wordDict)
        def dfs(s):
            if len(s) == 0:
                return True
            for word in wordDict:
                if len(word) <= len(s):
                    if s.startswith(word):
                        if dfs(s[len(word):]):
                            return True
            return False
        return dfs(s)

而上面遞迴的方式存在著重複的子問題，可以透過記憶法的方式優化使用自頂向下的動態規劃來進一步提升效率。

這是我第二次想到的方法，其實可能更簡單，那就是我只要傳指針的位置就好，不用把整個字串都傳入，之前的寫法中，我都要加入檢查當前字典的字有沒有比目標還短？如果只要傳指針的時候，在傳入後檢查有沒有越位即可。

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:

        def dp(i):
            if i == len(s):
                return True
            if i > len(s):
                return False
            
            for word in wordDict:
                if s[i:].startswith(word):
                    if dp(i+len(word)):
                        return True
            return False
        
        return dp(0)

但是說真的，其實那個檢查越位的情況也根本不用考慮，因為如果是越位的情況，根本不可能滿足 s[i:].startswith(word) 的條件，也就不會進入到下一層遞迴。

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        
        def dp(i):
            if i == len(s):
                return True
            
            for word in wordDict:
                if s[i:].startswith(word):
                    if dp(i+len(word)):
                        return True
            return False
        
        return dp(0)

自頂向下

第一次的做法，把事情想得太複雜了。

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        
        wordDict = set(wordDict)

        @cache
        def dfs(i):
            if i == len(s):
                return True
            for word in wordDict:
                if len(s) - i >= len(word):
                    if ss[i:].startswith(word):
                        if dfs(i + len(word)):
                            return True
            return False
        
        return dfs(0)

第二次的做法，很多的地方都精簡掉了，邏輯也不會太複雜。

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        
        def dp(i):
            if i == len(s):
                return True
            
            for word in wordDict:
                if s[i:].startswith(word):
                    if dp(i+len(word)):
                        return True
            return False
        
        return dp(0)

自底向上

做法有點不直覺，處理的邏輯是一步一步走，去檢查每一個位置，有沒有機會可以用任何字典中的單字拼起來。檢查的邏輯如下：

例如：我站在某位置 j ，接著我就從位置 i = 0 一路檢查到位置 j ，看看有沒有辦法在位置 i 的地方其中 s[i:j] 剛好在字典裡面，但是這樣還不夠，那就是在位置 i 的地方，也要有字串可以到達才夠，如果兩個條件都滿足，那 dp[j] 就會是 True ，代表可以到達這個地方。

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:

        wordDict = set(wordDict)

        dp = [False] * (len(s) + 1)
        dp[0] = True

        for end in range(1, len(s)+1):
            for start in range(end):
                if dp[start] and s[start:end] in wordDict:
                    dp[end] = True
                    break

        return dp[len(s)]

回溯法

這一題其實也可以用回溯法來寫。參考 140. Word Break II

補充

自底向上只需要回頭看「最長的單字」那麼遠

上面那版的內層 for start in range(end) 會從 0 一路掃到 end，但比最長的單字還長的子字串永遠不可能在字典裡 —— 切出來、算完 hash、再發現不在，全是白工。

所以內層的起點可以有下界：

L = max(map(len, wordDict))                       # 最長的單字有多長

for end in range(1, len(s)+1):
    for start in range(max(0, end - L), end):     # 只回頭看 L 格
        if dp[start] and s[start:end] in wordDict:
            dp[end] = True
            break

len(s) = 300、1000 個單字（LeetCode 上限）、答案 False 的測資，實測 4.35 ms → 0.34 ms。

會差這麼多是因為 s[start:end] in wordDict 不是 $O (1)$ —— 它要先切出一份子字串（ $O (e n d - s t a r t)$ ），再算它的 hash（也是 $O (e n d - s t a r t)$ ）。原本的寫法會產生 $O (n^{2})$ 個子字串、每個最長到 $n$ ；加了下界之後，長度一律不超過 L。

另一個方向：掃單字而不是掃 start

for end in range(1, len(s)+1):
    for w in wordDict:
        if len(w) <= end and dp[end - len(w)] and s.startswith(w, end - len(w)):
            dp[end] = True
            break

startswith 不會另外配置子字串，但速度的關鍵不在這裡（實測它其實比切片比對還慢一點）—— 差別在內層跑的是單字數 m，所以單字少的時候大贏、單字多的時候反而輸：同一組測資，1000 個單字是 3.15 ms（比上面的 0.34 ms 慢），只有 10 個單字時是 0.05 ms。

判準：內層跑「回頭 L 格」還是「m 個單字」，挑小的那個。 這題 LeetCode 保證 L ≤ 20、m ≤ 1000，所以通常是加下界的切片版比較穩。

複雜度

設 $n$ 是 s 的長度、 $m$ 是單字數、 $L$ 是最長的單字長度。

純遞迴

時間 $O (2^{n})$ 上界 — 每個位置都可以是切點或不是，而且沒有記憶，同一個 i 會被不同的切法重複算
空間 $O (n)$ — 遞迴深度，每個單字至少吃掉一個字元

自頂向下

時間 $O (n \times m \times L)$ — 狀態只有 n + 1 個，每個狀態掃 m 個單字、每次比對最多 $O (L)$
空間 $O (n)$ — cache 加上遞迴堆疊

自底向上

時間 $O (n^{3})$ — 兩層迴圈產生 $O (n^{2})$ 個子字串，每個切片加 hash 是 $O (n)$ ；套上補充裡的下界之後降到 $O (n \times L^{2})$
空間 $O (n)$ — dp 陣列（不含 wordDict 本身）

自頂向下和自底向上的差別值得注意：一個掃單字、一個掃切點，所以 m 很大時前者吃虧、n 很大時後者吃虧。