140. 单词拆分 II
题目描述
输入字符串 s 和字典 wordDict。在 s 中插入空格，把它分成若干单词，要求每个单词都在字典里。字典里的单词可以重复使用。
每种分法写成一个句子：单词之间用一个空格隔开。返回所有可能的句子，顺序不限；一种都没有时返回 []。
示例 1
输入：s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"] 输出：["cat sand dog","cats and dog"]
解释：可以分成 cat sand dog 或 cats and dog。
示例 2
输入：s = "pineapplepenapple" wordDict = ["apple","pen","applepen","pine","pineapple"] 输出：["pine apple pen apple","pine applepen apple","pineapple pen apple"]
解释：共有三种分法，其中 apple 可以重复使用。
示例 3
输入：s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] 输出：[]
解释：无法把整个字符串分成字典里的单词。
数据范围
1 <= s.length <= 201 <= wordDict.length <= 10001 <= wordDict[i].length <= 10s和wordDict[i]只含小写英文字母。wordDict中没有重复单词。
解题思路：回溯枚举切分
回溯。dfs(start) 表示 s[0:start] 已经切好并放在 path 里。枚举下一个单词的结束位置 end，只要 s[start:end] 在字典里，就把它放进 path 并递归 dfs(end)，返回后弹出。start 等于 len(s) 时，用空格拼接 path 记录一个句子。
为什么正确
path 中的单词依次拼接恰好等于 s[0:start]，且每个都在字典中。
复杂度分析
最坏情况下句子数量是指数级，时间 O(2^n · n)；递归深度 O(n)。
易错点
句子里的空格只能出现在单词之间，用 join 拼接最稳妥；另外不要在找到一个句子后就停，要枚举完所有 end。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
words = set(wordDict)
res, path = [], []
def dfs(start):
if start == len(s):
res.append(' '.join(path))
return
for end in range(start + 1, len(s) + 1):
w = s[start:end]
if w in words:
path.append(w)
dfs(end)
path.pop()
dfs(0)
return resclass Solution {
Set<String> words;
List<String> res = new ArrayList<>();
List<String> path = new ArrayList<>();
String s;
public List<String> wordBreak(String s, List<String> wordDict) {
this.s = s;
words = new HashSet<>(wordDict);
dfs(0);
return res;
}
void dfs(int start) {
if (start == s.length()) {
res.add(String.join(" ", path));
return;
}
for (int end = start + 1; end <= s.length(); end++) {
String w = s.substring(start, end);
if (words.contains(w)) {
path.add(w);
dfs(end);
path.remove(path.size() - 1);
}
}
}
}class Solution {
public:
vector<string> wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> words(wordDict.begin(), wordDict.end());
vector<string> res, path;
function<void(int)> dfs = [&](int start) {
if (start == (int)s.size()) {
string one;
for (size_t k = 0; k < path.size(); k++) one += (k ? " " : "") + path[k];
res.push_back(one);
return;
}
for (int end = start + 1; end <= (int)s.size(); end++) {
string w = s.substr(start, end - start);
if (words.count(w)) {
path.push_back(w);
dfs(end);
path.pop_back();
}
}
};
dfs(0);
return res;
}
};func wordBreak(s string, wordDict []string) []string {
words := map[string]bool{}
for _, w := range wordDict {
words[w] = true
}
res, path := []string{}, []string{}
var dfs func(start int)
dfs = func(start int) {
if start == len(s) {
one := ""
for k, p := range path {
if k > 0 {
one += " "
}
one += p
}
res = append(res, one)
return
}
for end := start + 1; end <= len(s); end++ {
w := s[start:end]
if words[w] {
path = append(path, w)
dfs(end)
path = path[:len(path)-1]
}
}
}
dfs(0)
return res
}var wordBreak = function(s, wordDict) {
const words = new Set(wordDict);
const res = [], path = [];
const dfs = (start) => {
if (start === s.length) {
res.push(path.join(' '));
return;
}
for (let end = start + 1; end <= s.length; end++) {
const w = s.slice(start, end);
if (words.has(w)) {
path.push(w);
dfs(end);
path.pop();
}
}
};
dfs(0);
return res;
};function wordBreak(s: string, wordDict: string[]): string[] {
const words = new Set(wordDict);
const res: string[] = [], path: string[] = [];
const dfs = (start: number): void => {
if (start === s.length) {
res.push(path.join(' '));
return;
}
for (let end = start + 1; end <= s.length; end++) {
const w = s.slice(start, end);
if (words.has(w)) {
path.push(w);
dfs(end);
path.pop();
}
}
};
dfs(0);
return res;
}其他解法
回溯法空间小但会重复搜索无解或共享的后缀；记忆化用空间换时间，每个后缀只展开一次。
解法 2：记忆化搜索 时间 O(n·2ⁿ)，空间 O(n·2ⁿ)
suffix(start) 返回从 start 开始的后缀的所有拆分句子。枚举第一个单词 s[start:end]，若在字典中，就把它拼到 suffix(end) 的每个句子前面。每个 start 的结果只算一次并缓存。
同一后缀被多条前缀路径共用时，避免重复搜索。最坏情况输出本身是指数级，缓存也会占用同量级空间。
from functools import lru_cache
from typing import List
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
words = set(wordDict)
n = len(s)
@lru_cache(None)
def suffix(start):
if start == n:
return [[]]
res = []
for end in range(start + 1, n + 1):
w = s[start:end]
if w in words:
for rest in suffix(end):
res.append([w] + rest)
return res
return [' '.join(p) for p in suffix(0)]class Solution {
private Set<String> words;
private Map<Integer, List<String>> memo = new HashMap<>();
private String s;
public List<String> wordBreak(String s, List<String> wordDict) {
this.s = s;
words = new HashSet<>(wordDict);
return suffix(0);
}
private List<String> suffix(int start) {
if (memo.containsKey(start)) return memo.get(start);
List<String> res = new ArrayList<>();
int n = s.length();
for (int end = start + 1; end <= n; end++) {
String w = s.substring(start, end);
if (!words.contains(w)) continue;
if (end == n) {
res.add(w);
} else {
for (String rest : suffix(end)) res.add(w + " " + rest);
}
}
memo.put(start, res);
return res;
}
}class Solution {
unordered_set<string> words;
unordered_map<int, vector<string>> memo;
string s;
const vector<string>& suffix(int start) {
auto it = memo.find(start);
if (it != memo.end()) return it->second;
vector<string> res;
int n = s.size();
for (int end = start + 1; end <= n; end++) {
string w = s.substr(start, end - start);
if (!words.count(w)) continue;
if (end == n) {
res.push_back(w);
} else {
for (const string& rest : suffix(end)) res.push_back(w + " " + rest);
}
}
return memo[start] = res;
}
public:
vector<string> wordBreak(string s, vector<string>& wordDict) {
this->s = s;
words = unordered_set<string>(wordDict.begin(), wordDict.end());
memo.clear();
return suffix(0);
}
};func wordBreak(s string, wordDict []string) []string {
words := map[string]bool{}
for _, w := range wordDict {
words[w] = true
}
n := len(s)
memo := map[int][]string{}
var suffix func(start int) []string
suffix = func(start int) []string {
if r, ok := memo[start]; ok {
return r
}
res := []string{}
for end := start + 1; end <= n; end++ {
w := s[start:end]
if !words[w] {
continue
}
if end == n {
res = append(res, w)
} else {
for _, rest := range suffix(end) {
res = append(res, w+" "+rest)
}
}
}
memo[start] = res
return res
}
return suffix(0)
}var wordBreak = function(s, wordDict) {
const words = new Set(wordDict);
const n = s.length;
const memo = new Map();
const suffix = (start) => {
if (memo.has(start)) return memo.get(start);
const res = [];
for (let end = start + 1; end <= n; end++) {
const w = s.slice(start, end);
if (!words.has(w)) continue;
if (end === n) res.push(w);
else for (const rest of suffix(end)) res.push(w + ' ' + rest);
}
memo.set(start, res);
return res;
};
return suffix(0);
};function wordBreak(s: string, wordDict: string[]): string[] {
const words = new Set(wordDict);
const n = s.length;
const memo = new Map<number, string[]>();
const suffix = (start: number): string[] => {
if (memo.has(start)) return memo.get(start)!;
const res: string[] = [];
for (let end = start + 1; end <= n; end++) {
const w = s.slice(start, end);
if (!words.has(w)) continue;
if (end === n) res.push(w);
else for (const rest of suffix(end)) res.push(w + ' ' + rest);
}
memo.set(start, res);
return res;
};
return suffix(0);
}