LeetCode 140: Word Break II (DP Feasibility + DFS Sentence Reconstruction)
LeetCode 140Dynamic ProgrammingBacktrackingStringToday we solve LeetCode 140 - Word Break II.
Source: https://leetcode.com/problems/word-break-ii/
English
Problem Summary
Given a string s and a dictionary wordDict, return all possible sentences by inserting spaces so every segment is a valid dictionary word.
Key Insight
Direct DFS over all split positions explodes quickly. We first compute a suffix-feasibility DP array to prune impossible branches, then run memoized DFS to build all valid sentences.
Algorithm (DP + DFS)
1) Put all words into a hash set for O(1) lookup.
2) Compute canBreak[i]: whether s[i..n) can be segmented.
3) DFS(index): enumerate all end where substring is in dict and canBreak[end] is true.
4) Recursively collect sentence tails and prepend current word.
5) Memoize DFS results by index to avoid repeated reconstruction.
Complexity Analysis
Let N be string length. Feasibility DP is O(N^2). DFS output size can be exponential in worst case, which is unavoidable because we must return every sentence.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public List wordBreak(String s, List wordDict) {
int n = s.length();
Set dict = new HashSet<>(wordDict);
boolean[] canBreak = new boolean[n + 1];
canBreak[n] = true;
for (int i = n - 1; i >= 0; i--) {
for (int end = i + 1; end <= n; end++) {
if (dict.contains(s.substring(i, end)) && canBreak[end]) {
canBreak[i] = true;
break;
}
}
}
Map> memo = new HashMap<>();
return dfs(0, s, dict, canBreak, memo);
}
private List dfs(int i, String s, Set dict, boolean[] canBreak,
Map> memo) {
if (memo.containsKey(i)) return memo.get(i);
int n = s.length();
List res = new ArrayList<>();
if (i == n) {
res.add("");
memo.put(i, res);
return res;
}
for (int end = i + 1; end <= n; end++) {
String word = s.substring(i, end);
if (!dict.contains(word) || !canBreak[end]) continue;
for (String tail : dfs(end, s, dict, canBreak, memo)) {
res.add(tail.isEmpty() ? word : word + " " + tail);
}
}
memo.put(i, res);
return res;
}
} func wordBreak(s string, wordDict []string) []string {
n := len(s)
dict := map[string]bool{}
for _, w := range wordDict {
dict[w] = true
}
canBreak := make([]bool, n+1)
canBreak[n] = true
for i := n - 1; i >= 0; i-- {
for end := i + 1; end <= n; end++ {
if dict[s[i:end]] && canBreak[end] {
canBreak[i] = true
break
}
}
}
memo := map[int][]string{}
var dfs func(int) []string
dfs = func(i int) []string {
if v, ok := memo[i]; ok {
return v
}
if i == n {
return []string{""}
}
res := []string{}
for end := i + 1; end <= n; end++ {
word := s[i:end]
if !dict[word] || !canBreak[end] {
continue
}
tails := dfs(end)
for _, tail := range tails {
if tail == "" {
res = append(res, word)
} else {
res = append(res, word+" "+tail)
}
}
}
memo[i] = res
return res
}
return dfs(0)
}class Solution {
public:
vector wordBreak(string s, vector& wordDict) {
int n = (int)s.size();
unordered_set dict(wordDict.begin(), wordDict.end());
vector canBreak(n + 1, false);
canBreak[n] = true;
for (int i = n - 1; i >= 0; --i) {
for (int end = i + 1; end <= n; ++end) {
if (dict.count(s.substr(i, end - i)) && canBreak[end]) {
canBreak[i] = true;
break;
}
}
}
unordered_map> memo;
return dfs(0, s, dict, canBreak, memo);
}
private:
vector dfs(int i, const string& s, unordered_set& dict,
vector& canBreak,
unordered_map>& memo) {
if (memo.count(i)) return memo[i];
int n = (int)s.size();
vector res;
if (i == n) {
res.push_back("");
memo[i] = res;
return res;
}
for (int end = i + 1; end <= n; ++end) {
string word = s.substr(i, end - i);
if (!dict.count(word) || !canBreak[end]) continue;
vector tails = dfs(end, s, dict, canBreak, memo);
for (const string& tail : tails) {
if (tail.empty()) res.push_back(word);
else res.push_back(word + " " + tail);
}
}
memo[i] = res;
return res;
}
}; from functools import lru_cache
from typing import List
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
n = len(s)
words = set(wordDict)
can_break = [False] * (n + 1)
can_break[n] = True
for i in range(n - 1, -1, -1):
for end in range(i + 1, n + 1):
if s[i:end] in words and can_break[end]:
can_break[i] = True
break
@lru_cache(None)
def dfs(i: int) -> List[str]:
if i == n:
return [""]
res = []
for end in range(i + 1, n + 1):
word = s[i:end]
if word not in words or not can_break[end]:
continue
for tail in dfs(end):
res.append(word if tail == "" else word + " " + tail)
return res
return dfs(0)var wordBreak = function(s, wordDict) {
const n = s.length;
const dict = new Set(wordDict);
const canBreak = Array(n + 1).fill(false);
canBreak[n] = true;
for (let i = n - 1; i >= 0; i--) {
for (let end = i + 1; end <= n; end++) {
if (dict.has(s.slice(i, end)) && canBreak[end]) {
canBreak[i] = true;
break;
}
}
}
const memo = new Map();
const dfs = (i) => {
if (memo.has(i)) return memo.get(i);
if (i === n) return [""];
const res = [];
for (let end = i + 1; end <= n; end++) {
const word = s.slice(i, end);
if (!dict.has(word) || !canBreak[end]) continue;
const tails = dfs(end);
for (const tail of tails) {
res.push(tail === "" ? word : word + " " + tail);
}
}
memo.set(i, res);
return res;
};
return dfs(0);
};中文
题目概述
给定字符串 s 和词典 wordDict，请返回所有可能的合法句子：通过插入空格，使得每一段都在词典中。
核心思路
直接回溯会非常慢。先用 DP 判断每个后缀是否可拆分（可行性剪枝），再做带记忆化的 DFS 重建所有句子。
算法步骤（DP + DFS）
1）将词典放入哈希集合。
2）计算 canBreak[i]，表示后缀 s[i..n) 是否可拆。
3）DFS(i)：枚举所有 end，若 s[i..end) 在词典且 canBreak[end] 为真，则继续。
4）把当前单词与子问题返回的尾句拼接。
5）对每个起点 i 记忆化，避免重复重建。
复杂度分析
可行性 DP 为 O(N^2)。DFS 的最坏输出可能指数级（题目要求返回全部句子，因此不可避免）。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public List wordBreak(String s, List wordDict) {
int n = s.length();
Set dict = new HashSet<>(wordDict);
boolean[] canBreak = new boolean[n + 1];
canBreak[n] = true;
for (int i = n - 1; i >= 0; i--) {
for (int end = i + 1; end <= n; end++) {
if (dict.contains(s.substring(i, end)) && canBreak[end]) {
canBreak[i] = true;
break;
}
}
}
Map> memo = new HashMap<>();
return dfs(0, s, dict, canBreak, memo);
}
private List dfs(int i, String s, Set dict, boolean[] canBreak,
Map> memo) {
if (memo.containsKey(i)) return memo.get(i);
int n = s.length();
List res = new ArrayList<>();
if (i == n) {
res.add("");
memo.put(i, res);
return res;
}
for (int end = i + 1; end <= n; end++) {
String word = s.substring(i, end);
if (!dict.contains(word) || !canBreak[end]) continue;
for (String tail : dfs(end, s, dict, canBreak, memo)) {
res.add(tail.isEmpty() ? word : word + " " + tail);
}
}
memo.put(i, res);
return res;
}
} func wordBreak(s string, wordDict []string) []string {
n := len(s)
dict := map[string]bool{}
for _, w := range wordDict {
dict[w] = true
}
canBreak := make([]bool, n+1)
canBreak[n] = true
for i := n - 1; i >= 0; i-- {
for end := i + 1; end <= n; end++ {
if dict[s[i:end]] && canBreak[end] {
canBreak[i] = true
break
}
}
}
memo := map[int][]string{}
var dfs func(int) []string
dfs = func(i int) []string {
if v, ok := memo[i]; ok {
return v
}
if i == n {
return []string{""}
}
res := []string{}
for end := i + 1; end <= n; end++ {
word := s[i:end]
if !dict[word] || !canBreak[end] {
continue
}
tails := dfs(end)
for _, tail := range tails {
if tail == "" {
res = append(res, word)
} else {
res = append(res, word+" "+tail)
}
}
}
memo[i] = res
return res
}
return dfs(0)
}class Solution {
public:
vector wordBreak(string s, vector& wordDict) {
int n = (int)s.size();
unordered_set dict(wordDict.begin(), wordDict.end());
vector canBreak(n + 1, false);
canBreak[n] = true;
for (int i = n - 1; i >= 0; --i) {
for (int end = i + 1; end <= n; ++end) {
if (dict.count(s.substr(i, end - i)) && canBreak[end]) {
canBreak[i] = true;
break;
}
}
}
unordered_map> memo;
return dfs(0, s, dict, canBreak, memo);
}
private:
vector dfs(int i, const string& s, unordered_set& dict,
vector& canBreak,
unordered_map>& memo) {
if (memo.count(i)) return memo[i];
int n = (int)s.size();
vector res;
if (i == n) {
res.push_back("");
memo[i] = res;
return res;
}
for (int end = i + 1; end <= n; ++end) {
string word = s.substr(i, end - i);
if (!dict.count(word) || !canBreak[end]) continue;
vector tails = dfs(end, s, dict, canBreak, memo);
for (const string& tail : tails) {
if (tail.empty()) res.push_back(word);
else res.push_back(word + " " + tail);
}
}
memo[i] = res;
return res;
}
}; from functools import lru_cache
from typing import List
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
n = len(s)
words = set(wordDict)
can_break = [False] * (n + 1)
can_break[n] = True
for i in range(n - 1, -1, -1):
for end in range(i + 1, n + 1):
if s[i:end] in words and can_break[end]:
can_break[i] = True
break
@lru_cache(None)
def dfs(i: int) -> List[str]:
if i == n:
return [""]
res = []
for end in range(i + 1, n + 1):
word = s[i:end]
if word not in words or not can_break[end]:
continue
for tail in dfs(end):
res.append(word if tail == "" else word + " " + tail)
return res
return dfs(0)var wordBreak = function(s, wordDict) {
const n = s.length;
const dict = new Set(wordDict);
const canBreak = Array(n + 1).fill(false);
canBreak[n] = true;
for (let i = n - 1; i >= 0; i--) {
for (let end = i + 1; end <= n; end++) {
if (dict.has(s.slice(i, end)) && canBreak[end]) {
canBreak[i] = true;
break;
}
}
}
const memo = new Map();
const dfs = (i) => {
if (memo.has(i)) return memo.get(i);
if (i === n) return [""];
const res = [];
for (let end = i + 1; end <= n; end++) {
const word = s.slice(i, end);
if (!dict.has(word) || !canBreak[end]) continue;
const tails = dfs(end);
for (const tail of tails) {
res.push(tail === "" ? word : word + " " + tail);
}
}
memo.set(i, res);
return res;
};
return dfs(0);
};
Comments