本文完整拆解 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 <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20sandwordDict[i]consist of only lowercase English letters.- All the strings of
wordDictare 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 演算法步驟
- 把 wordDict 放進集合,建立長度 n+1 的布林陣列 dp,dp[0] = true。
- 外層 i 從 1 走到 n。
- 內層 j 從 0 走到 i-1,若 dp[j] 為真且 s.slice(j, i) 在集合中,就把 dp[i] 設為 true 並 break。
- 最後回傳 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) | 本文採用 |
