LeetCode 139: Word Break ·

基本資料
#

難易度: medium 第一次嘗試：2026-04-28 來源：Day 15 learning note

學習脈絡
#

這篇是從 learning note 裡該 LeetCode 題目的段落重新整理出來的版本。我保留當天筆記中的修正點、比較點、容易犯錯的地方，並移除同一天其他非 LeetCode 主題，避免文章內容混題。

當天筆記摘錄
#

Problem 1 - LC 139 Word Break
#

Status: Good enough after implementation repair.
Pattern: Prefix DP / segmentation DP.

Why DP Fits
#

Whether a prefix can be segmented depends on whether a smaller prefix was already segmentable and whether the current suffix matches a dictionary word.

State
#

dp[i] = whether s[:i] can be segmented using wordDict

Base Case
#

dp[0] = True

Meaning:

the empty prefix is segmentable

Transition
#

For each index i and each word:

if i >= len(word) and dp[i - len(word)] and s[i - len(word):i] == word:
    dp[i] = True

Complexity
#

Time: O(n * m * L)
Space: O(n)

Where:

n = len(s)
m = len(wordDict)
L = word length / substring compare cost

Main Implementation Repairs
#

dp size must be:

[False] * (len(s) + 1)

loop bound must use:

range(1, len(s) + 1)

index must use:

dp[i - len(word)]

not:

dp[i - word]

Interview-Ready Explanation
#

I define dp[i] as whether the prefix s[:i] can be segmented. The empty prefix is true. For each position, I try each dictionary word. If the prefix before that word is already segmentable and the current suffix equals the word, then the current prefix is segmentable too.

正確解法
#

上面的筆記保留了推理脈絡和當天需要修正的點。下面是我會提交的版本。

from typing import List

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        words = set(wordDict)
        max_len = max(map(len, words), default=0)
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True

        for i in range(1, n + 1):
            for length in range(1, min(max_len, i) + 1):
                if dp[i - length] and s[i - length:i] in words:
                    dp[i] = True
                    break

        return dp[n]