Word Break 解題教學:3 種解法完整比較|LeetCode 139 Best Practice

Word Break 解題教學示意圖|LeetCode 139

本文完整拆解 LeetCode 139 Word Break 的解法:從解題思路、演算法步驟到時間與空間複雜度,並整理邊界情況與 3 種解法比較,幫你把 Word Break 一次弄懂。

Explore diverse LeetCode solutions in Python, C++, JavaScript, SQL, and TypeScript. Ideal for interview prep, learning, and code practice in multiple programming languages. Github Repo Link


Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false

Constraints:

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s and wordDict[i] consist of only lowercase English letters.
  • All the strings of wordDict are unique.

Python

				
					# Tries
# time complexity: O(n^2 + m*k)
# space complexity: O(n + m*k)
from typing import List


class TrieNode:
    def __init__(self):
        self.isWord = False
        self.children = {}


class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        root = TrieNode()
        for word in wordDict:
            curr = root
            for c in word:
                if c not in curr.children:
                    curr.children[c] = TrieNode()
                curr = curr.children[c]
            curr.isWord = True

        dp = [False] * len(s)
        for i in range(len(s)):
            if i == 0 or dp[i-1]:
                curr = root
                for j in range(i, len(s)):
                    c = s[j]
                    if c not in curr.children:
                        break
                    curr = curr.children[c]
                    if curr.isWord:
                        dp[j] = True
        return dp[-1]

# DP 2
# time complexity: O(n^3 +m*k)
# space complexity: O(n+m*k)
# from typing import List
# class Solution:
#     def wordBreak(self, s: str, wordDict: List[str]) -> bool:
#         sLen = len(s)
#         words = set(wordDict)
#         dp = [False] * (sLen + 1)
#         dp[0] = True
#         for i in range(1, sLen + 1):
#             for j in range(i):
#                 if dp[j] and s[j:i] in words:
#                     dp[i] = True
#                     break
#         return True


# DP 1
# time complexity: O(n*m*k)
# space complexity: O(n)
#
# from typing import List
# class Solution:
#     def wordBreak(self, s: str, wordDict: List[str]) -> bool:
#         sLen = len(s)
#         dp = [False] * sLen
#         for i in range(sLen):
#             for word in wordDict:
#                 wordLen = len(word)
#                 if i < wordLen - 1:
#                     continue
#                 if i == wordLen - 1 or dp[i-wordLen]:
#                     if s[i-wordLen+1:i + 1] == word:
#                         dp[i] = True
#                         break
#         print(dp)
#         return dp[sLen-1]


# BFS
# time complexity: O(n^3 + m*k)
# space complexity: O(n+m*k)
#
# from collections import deque
# from typing import List
# class Solution:
#     def wordBreak(self, s: str, wordDict: List[str]) -> bool:
#         words = set(wordDict)
#         queue = deque([0])
#         seen = set()
#         while queue:
#             start = queue.popleft()
#             if start == len(s):
#                 return True
#             for end in range(start + 1, len(s) + 1):
#                 if end in seen:
#                     continue
#                 if s[start:end] in words:
#                     queue.append(end)
#                     seen.add(end)
#         return False


S = "applepenapple"
WordDict = ["apple", "pen"]


print(Solution().wordBreak(S, WordDict))
				
			

Word Break 解題思路

判斷字串能不能被字典完整切開,是典型的線性 DP:令 dp[i] 代表前 i 個字元能否被切開。要讓 dp[i] 成立,只需要找到某個切點 j,使得 dp[j] 為真且 s[j..i) 這一段是字典中的單字。把字典放進集合,每次查詢就是 O(1)。

Word Break 演算法步驟

  1. 把 wordDict 放進集合,建立長度 n+1 的布林陣列 dp,dp[0] = true。
  2. 外層 i 從 1 走到 n。
  3. 內層 j 從 0 走到 i-1,若 dp[j] 為真且 s.slice(j, i) 在集合中,就把 dp[i] 設為 true 並 break。
  4. 最後回傳 dp[n]。

Word Break 複雜度分析

項目複雜度
時間複雜度O(n²·k)
空間複雜度O(n)

雙層迴圈是 O(n²),每次切片與雜湊查詢約 O(k)(k 為子字串長度),整體為 O(n²·k)。dp 陣列佔 O(n),集合佔字典大小。若改用 Trie 可避免切片成本。

Word Break 的邊界情況與常見錯誤

  • dp[0] 必須初始化為 true,代表空字串可被切開。
  • 內層找到一個可行切點就能 break,不必找完。
  • 字典單字可能重複,用集合自動去重。
  • 純遞迴不加記憶化會重複計算,最壞達到指數級。

Word Break 其他解法比較

解法時間空間說明
回溯列舉所有切法O(2^n)O(n)指數爆炸
記憶化遞迴O(n²·k)O(n)與 DP 等價,寫法更直覺
線性 DP + 集合O(n²·k)O(n)本文採用