LeetCode 139: Word Break (Dynamic Programming)
LeetCode 139DPStringToday we solve LeetCode 139 - Word Break.
Source: https://leetcode.com/problems/word-break/
English
Problem Summary
Given a string s and a dictionary wordDict, determine whether s can be segmented into one or more dictionary words.
Key Insight
Think in prefixes. Let dp[i] mean whether prefix s[0..i) can be segmented. For each end index i, try a split point j: if dp[j] is true and s[j..i) is in dictionary, then dp[i] = true.
Brute Force and Limitations
Naively trying every split recursively causes repeated work and may become exponential. Memoization helps, but bottom-up DP gives a direct and stable implementation.
Optimal Algorithm Steps
1) Put all dictionary words into a hash set for O(1) lookup.
2) Initialize dp[0] = true (empty prefix is segmentable).
3) For each i from 1 to n, scan j from 0 to i-1.
4) If dp[j] and s.substring(j, i) is in set, set dp[i] = true and break.
Complexity Analysis
Time: O(n^2) transitions (substring cost depends on language/runtime).
Space: O(n + m), where m is dictionary storage.
Common Pitfalls
- Forgetting dp[0] = true.
- Using list lookup instead of hash set, causing major slowdown.
- Not breaking after finding a valid split, doing unnecessary work.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
import java.util.HashSet;
import java.util.List;
import java.util.Set;
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> dict = new HashSet<>(wordDict);
int n = s.length();
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && dict.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
}func wordBreak(s string, wordDict []string) bool {
dict := make(map[string]bool, len(wordDict))
for _, w := range wordDict {
dict[w] = true
}
n := len(s)
dp := make([]bool, n+1)
dp[0] = true
for i := 1; i <= n; i++ {
for j := 0; j < i; j++ {
if dp[j] && dict[s[j:i]] {
dp[i] = true
break
}
}
}
return dp[n]
}class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> dict(wordDict.begin(), wordDict.end());
int n = (int)s.size();
vector<bool> dp(n + 1, false);
dp[0] = true;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < i; ++j) {
if (dp[j] && dict.count(s.substr(j, i - j))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
};class Solution:
def wordBreak(self, s: str, wordDict: list[str]) -> bool:
dict_set = set(wordDict)
n = len(s)
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
for j in range(i):
if dp[j] and s[j:i] in dict_set:
dp[i] = True
break
return dp[n]var wordBreak = function(s, wordDict) {
const dict = new Set(wordDict);
const n = s.length;
const dp = new Array(n + 1).fill(false);
dp[0] = true;
for (let i = 1; i <= n; i++) {
for (let j = 0; j < i; j++) {
if (dp[j] && dict.has(s.slice(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[n];
};中文
题目概述
给定字符串 s 和字典 wordDict，判断 s 是否可以被拆分为一个或多个字典中的单词。
核心思路
使用前缀动态规划。定义 dp[i] 表示前缀 s[0..i) 是否可拆分。枚举分割点 j：若 dp[j] = true 且 s[j..i) 在字典中，则 dp[i] = true。
暴力解法与不足
递归枚举所有切分会产生大量重复子问题，最坏接近指数复杂度。虽然记忆化可以优化，但自底向上的 DP 结构更清晰、可控。
最优算法步骤
1）先把字典放入哈希集合，便于快速判断。
2）初始化 dp[0] = true。
3）遍历 i = 1..n，并遍历 j = 0..i-1。
4）若 dp[j] 为真且子串 s[j:i] 在集合中，则置 dp[i] = true 并提前退出内层循环。
复杂度分析
时间复杂度：O(n^2)（子串构造代价依语言实现而异）。
空间复杂度：O(n + m)，其中 m 为字典存储开销。
常见陷阱
- 忘记设置 dp[0] = true。
- 字典不使用哈希集合，导致查找过慢。
- 已经找到可行切分后仍继续枚举，浪费时间。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
import java.util.HashSet;
import java.util.List;
import java.util.Set;
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> dict = new HashSet<>(wordDict);
int n = s.length();
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && dict.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
}func wordBreak(s string, wordDict []string) bool {
dict := make(map[string]bool, len(wordDict))
for _, w := range wordDict {
dict[w] = true
}
n := len(s)
dp := make([]bool, n+1)
dp[0] = true
for i := 1; i <= n; i++ {
for j := 0; j < i; j++ {
if dp[j] && dict[s[j:i]] {
dp[i] = true
break
}
}
}
return dp[n]
}class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> dict(wordDict.begin(), wordDict.end());
int n = (int)s.size();
vector<bool> dp(n + 1, false);
dp[0] = true;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < i; ++j) {
if (dp[j] && dict.count(s.substr(j, i - j))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
};class Solution:
def wordBreak(self, s: str, wordDict: list[str]) -> bool:
dict_set = set(wordDict)
n = len(s)
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
for j in range(i):
if dp[j] and s[j:i] in dict_set:
dp[i] = True
break
return dp[n]var wordBreak = function(s, wordDict) {
const dict = new Set(wordDict);
const n = s.length;
const dp = new Array(n + 1).fill(false);
dp[0] = true;
for (let i = 1; i <= n; i++) {
for (let j = 0; j < i; j++) {
if (dp[j] && dict.has(s.slice(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[n];
};
Comments