单词拆分 II 图解题解

这道题到底在问什么

输入

s="catsanddog", dict=[cat,cats,and,sand,dog]

输出

["cats and dog","cat sand dog"]

输入

s="catsandog", dict=[cats,dog,sand,and,cat]

输出

[](尾部 "og" 拼不出)

先想最直接的笨办法

记住「枚举词典词切首段、递归拼后缀、memo 缓存起点结果」,下面看调用栈逐层展开。（动画第 3 步）

最优解：一步一步想明白

1. 3记住「枚举词典词切首段、递归拼后缀、memo 缓存起点结果」,下面看调用栈逐层展开。
2. 4调用 dfs(0):求从下标 0(灰色之后)开始能拼出的所有句子,压入调用栈。
3. 5在 dfs(0) 里试切词 "cat"(下标 0 到 2):它在词典里!接着递归 dfs(3) 求后缀 "sanddog" 的所有句子。
4. 6调用 dfs(3):求从下标 3(灰色之后)开始能拼出的所有句子,压入调用栈。
5. 7在 dfs(3) 里试切词 "sand"(下标 3 到 6):它在词典里!接着递归 dfs(7) 求后缀 "dog" 的所有句子。
6. 8调用 dfs(7):求从下标 7(灰色之后)开始能拼出的所有句子,压入调用栈。
7. 9在 dfs(7) 里试切词 "dog"(下标 7 到 9):它在词典里!接着递归 dfs(10) 求后缀 "" 的所有句子。
8. 10调用 dfs(10):求从下标 10(灰色之后)开始能拼出的所有句子,压入调用栈。
9. 11i=10 已到串尾,说明前面的词正好把整串拼完。直接返回 [""](一个空句子,成功标记),这是递归出口,不写入 memo。
10. 12dfs(10) 返回 1 个后缀句子,把 "dog" 拼到每个前面,dfs(7) 目前收集到 1 个句子。
11. 13dfs(7) 的所有切法试完,得到 1 个句子,写入 memo[7] 并返回,弹出调用栈。
12. 14dfs(7) 返回 1 个后缀句子,把 "sand" 拼到每个前面,dfs(3) 目前收集到 1 个句子。
13. 15dfs(3) 的所有切法试完,得到 1 个句子,写入 memo[3] 并返回,弹出调用栈。
14. 16dfs(3) 返回 1 个后缀句子,把 "cat" 拼到每个前面,dfs(0) 目前收集到 1 个句子。
15. 17在 dfs(0) 里试切词 "cats"(下标 0 到 3):它在词典里!接着递归 dfs(4) 求后缀 "anddog" 的所有句子。
16. 18调用 dfs(4):求从下标 4(灰色之后)开始能拼出的所有句子,压入调用栈。
17. 19在 dfs(4) 里试切词 "and"(下标 4 到 6):它在词典里!接着递归 dfs(7) 求后缀 "dog" 的所有句子。
18. 20到达 dfs(7),memo[7] 已有缓存,直接返回,不再展开(这正是记忆化省时的关键)。
19. 21dfs(7) 返回 1 个后缀句子,把 "and" 拼到每个前面,dfs(4) 目前收集到 1 个句子。
20. 22dfs(4) 的所有切法试完,得到 1 个句子,写入 memo[4] 并返回,弹出调用栈。
21. 23dfs(4) 返回 1 个后缀句子,把 "cats" 拼到每个前面,dfs(0) 目前收集到 2 个句子。
22. 24dfs(0) 的所有切法试完,得到 2 个句子,写入 memo[0] 并返回,弹出调用栈。
23. 25调用栈全部弹空,dfs(0) 返回最终答案:共 2 个句子:"cat sand dog"、"cats and dog"。记忆化让每个起点只算一次,把可能指数级的重复展开压了下来。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
from functools import lru_cache
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        words = set(wordDict)
        @lru_cache(None)
        def dfs(i: int):
            if i == len(s):
                return ['']
            ans = []
            for j in range(i + 1, len(s) + 1):
                word = s[i:j]
                if word in words:
                    for tail in dfs(j):
                        ans.append(word if not tail else word + ' ' + tail)
            return ans
        return dfs(0)

#include <functional>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> words(wordDict.begin(), wordDict.end());
        unordered_map<int, vector<string>> memo;
        function<vector<string>(int)> dfs = [&](int i) -> vector<string> {
            if (memo.count(i)) return memo[i];
            if (i == (int)s.size()) return vector<string>{""};
            vector<string> ans;
            for (int j = i + 1; j <= (int)s.size(); ++j) {
                string word = s.substr(i, j - i);
                if (words.count(word)) for (auto tail : dfs(j)) ans.push_back(tail.empty() ? word : word + " " + tail);
            }
            return memo[i] = ans;
        };
        return dfs(0);
    }
};

import java.util.*;
class Solution {
    Set<String> words;
    Map<Integer, List<String>> memo;
    String s;
    public List<String> wordBreak(String s, List<String> wordDict) {
        this.s = s; words = new HashSet<>(wordDict); memo = new HashMap<>();
        return dfs(0);
    }
    private List<String> dfs(int i) {
        if (memo.containsKey(i)) return memo.get(i);
        if (i == s.length()) return new ArrayList<>(Arrays.asList(""));
        List<String> ans = new ArrayList<>();
        for (int j = i + 1; j <= s.length(); j++) {
            String word = s.substring(i, j);
            if (words.contains(word)) for (String tail : dfs(j)) ans.add(tail.isEmpty() ? word : word + " " + tail);
        }
        memo.put(i, ans);
        return ans;
    }
}

复杂度

面试官可能追问