LeetCode 第140题：单词拆分 II

题目描述

给定一个字符串 s 和一个字符串字典 wordDict ，在字符串 s 中增加空格来构建一个句子，使得句子中所有的单词都在词典中。以任意顺序 返回所有这些可能的句子。

**注意：**词典中的同一个单词可能在分段中被重复使用多次。

难度

困难

题目链接

点击在LeetCode中查看题目

示例

示例 1：

输入:s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
输出:["cats and dog","cat sand dog"]

示例 2：

输入:s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
输出:["pine apple pen apple","pineapple pen apple","pine applepen apple"]
解释: 注意你可以重复使用字典中的单词。

示例 3：

输入:s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
输出:[]

提示

1 <= s.length <= 20
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 10
s 和 wordDict[i] 仅有小写英文字母组成
wordDict 中所有字符串都不同

解题思路

方法一：回溯 + 记忆化搜索

这道题是“单词拆分”的进阶版，要求返回所有可能的拆分结果。我们可以使用回溯算法结合记忆化搜索来解决这个问题。

关键点：

使用记忆化搜索判断字符串是否可以被拆分，避免重复计算
使用回溯算法构建所有可能的拆分结果
使用哈希表存储中间结果，提高效率

具体步骤：

创建一个哈希表memo，用于存储每个子串的所有可能拆分结果
定义递归函数wordBreak(s, start)，返回从start开始的子串的所有可能拆分结果
如果memo中已经有start对应的结果，直接返回
如果start等于s的长度，返回包含空字符串的列表
初始化一个空列表result，用于存储当前子串的所有可能拆分结果
遍历从start开始的所有可能的单词：
- 如果s[start…i]在字典中，递归处理s[i…]
- 将当前单词与后续拆分结果组合，加入result
将result存入memo并返回

时间复杂度：O(2^n)，其中n是字符串s的长度。在最坏情况下，可能有2^n种拆分方式。空间复杂度：O(n * 2^n)，需要存储所有可能的拆分结果。

方法二：动态规划 + 回溯

我们也可以先使用动态规划判断字符串是否可以被拆分，然后使用回溯算法构建所有可能的拆分结果。

关键点：

使用动态规划判断字符串是否可以被拆分
只对可以被拆分的子串进行回溯，减少不必要的计算
使用哈希表存储字典，提高查找效率

具体步骤：

使用动态规划判断字符串s是否可以被拆分（与“单词拆分”相同）
如果s不能被拆分，直接返回空列表
使用回溯算法构建所有可能的拆分结果：
- 定义递归函数backtrack(s, start, path)，其中start表示当前处理的起始位置，path表示当前的拆分路径
- 如果start等于s的长度，将当前路径加入结果集
- 遍历从start开始的所有可能的单词：
  - 如果s[start…i]在字典中且dp[i]为true，将该单词加入路径，并递归处理s[i…]
  - 回溯，移除最后一个单词，尝试下一种可能

时间复杂度：O(n * 2^n)，其中n是字符串s的长度。动态规划部分为O(n^2)，回溯部分最坏情况下为O(2^n)。空间复杂度：O(n * 2^n)，需要存储所有可能的拆分结果。

图解思路

记忆化搜索分析表

以示例1为例：s = “catsanddog”, wordDict = [“cat”,“cats”,“and”,“sand”,“dog”]

子串	可能的拆分结果	说明
“”	[“”]	空字符串的拆分结果为空字符串
“dog”	[“dog”]	“dog”在字典中，拆分结果为“dog”
“sand”	[“sand”]	“sand”在字典中，拆分结果为“sand”
“and”	[“and”]	“and”在字典中，拆分结果为“and”
“anddog”	[“and dog”]	“and”在字典中，后续“dog”的拆分结果为“dog”
“sanddog”	[“sand dog”]	“sand”在字典中，后续“dog”的拆分结果为“dog”
“cats”	[“cats”]	“cats”在字典中，拆分结果为“cats”
“cat”	[“cat”]	“cat”在字典中，拆分结果为“cat”
“catsanddog”	[“cats and dog”]	“cats”在字典中，后续“anddog”的拆分结果为“and dog”
“catsanddog”	[“cat sand dog”]	“cat”在字典中，后续“sanddog”的拆分结果为“sand dog”

回溯过程分析表

以示例1为例：s = “catsanddog”, wordDict = [“cat”,“cats”,“and”,“sand”,“dog”]

当前位置	当前路径	尝试的单词	操作	结果
0	[]	“cat”	添加“cat”到路径	[“cat”]
3	[“cat”]	“sand”	添加“sand”到路径	[“cat”, “sand”]
7	[“cat”, “sand”]	“dog”	添加“dog”到路径	[“cat”, “sand”, “dog”]
10	[“cat”, “sand”, “dog”]	-	到达字符串末尾，加入结果集	结果集：[“cat sand dog”]
7	[“cat”, “sand”]	-	回溯，移除“dog”	[“cat”, “sand”]
3	[“cat”]	-	回溯，移除“sand”	[“cat”]
0	[]	“cats”	添加“cats”到路径	[“cats”]
4	[“cats”]	“and”	添加“and”到路径	[“cats”, “and”]
7	[“cats”, “and”]	“dog”	添加“dog”到路径	[“cats”, “and”, “dog”]
10	[“cats”, “and”, “dog”]	-	到达字符串末尾，加入结果集	结果集：[“cat sand dog”, “cats and dog”]

代码实现

C# 实现

public class Solution {
    private Dictionary<int, List<string>> memo = new Dictionary<int, List<string>>();
    private HashSet<string> wordSet;
    
    public IList<string> WordBreak(string s, IList<string> wordDict) {
        wordSet = new HashSet<string>(wordDict);
        return DFS(s, 0);
    }
    
    private List<string> DFS(string s, int start) {
        if (memo.ContainsKey(start)) {
            return memo[start];
        }
        
        List<string> result = new List<string>();
        
        // 如果已经到达字符串末尾，返回包含空字符串的列表
        if (start == s.Length) {
            result.Add("");
            return result;
        }
        
        // 尝试所有可能的单词
        for (int end = start + 1; end <= s.Length; end++) {
            string word = s.Substring(start, end - start);
            if (wordSet.Contains(word)) {
                // 递归处理剩余部分
                List<string> subList = DFS(s, end);
                
                // 将当前单词与后续拆分结果组合
                foreach (string sub in subList) {
                    result.Add(string.IsNullOrEmpty(sub) ? word : word + " " + sub);
                }
            }
        }
        
        memo[start] = result;
        return result;
    }
}

Python 实现

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        word_set = set(wordDict)
        memo = {}
        
        def dfs(start):
            if start in memo:
                return memo[start]
            
            result = []
            
            # 如果已经到达字符串末尾，返回包含空字符串的列表
            if start == len(s):
                result.append("")
                return result
            
            # 尝试所有可能的单词
            for end in range(start + 1, len(s) + 1):
                word = s[start:end]
                if word in word_set:
                    # 递归处理剩余部分
                    sub_list = dfs(end)
                    
                    # 将当前单词与后续拆分结果组合
                    for sub in sub_list:
                        if sub:
                            result.append(word + " " + sub)
                        else:
                            result.append(word)
            
            memo[start] = result
            return result
        
        return dfs(0)

C++ 实现

class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        unordered_map<int, vector<string>> memo;
        
        function<vector<string>(int)> dfs = [&](int start) -> vector<string> {
            if (memo.count(start)) {
                return memo[start];
            }
            
            vector<string> result;
            
            // 如果已经到达字符串末尾，返回包含空字符串的列表
            if (start == s.length()) {
                result.push_back("");
                return result;
            }
            
            // 尝试所有可能的单词
            for (int end = start + 1; end <= s.length(); end++) {
                string word = s.substr(start, end - start);
                if (wordSet.count(word)) {
                    // 递归处理剩余部分
                    vector<string> subList = dfs(end);
                    
                    // 将当前单词与后续拆分结果组合
                    for (const string& sub : subList) {
                        if (sub.empty()) {
                            result.push_back(word);
                        } else {
                            result.push_back(word + " " + sub);
                        }
                    }
                }
            }
            
            memo[start] = result;
            return result;
        };
        
        return dfs(0);
    }
};

执行结果

C# 实现

执行用时：108 ms
内存消耗：40.2 MB

Python 实现

执行用时：36 ms
内存消耗：16.4 MB

C++ 实现

执行用时：0 ms
内存消耗：7.3 MB

性能对比

语言	执行用时	内存消耗	特点
C#	108 ms	40.2 MB	执行速度适中，内存消耗较高
Python	36 ms	16.4 MB	执行速度适中，内存消耗适中
C++	0 ms	7.3 MB	执行速度最快，内存消耗最低

代码亮点

🎯 使用记忆化搜索避免重复计算，提高效率
💡 巧妙处理空字符串的情况，简化代码逻辑
🔍 使用哈希表存储字典和中间结果，提高查找效率
🎨 代码结构清晰，逻辑易于理解

常见错误分析

🚫 没有使用记忆化搜索，导致大量重复计算，超时
🚫 没有正确处理空字符串的情况，导致结果错误
🚫 字符串拼接操作不正确，导致结果格式错误
🚫 没有使用哈希表存储字典，导致查找效率低下

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
回溯 + 记忆化搜索	O(2^n)	O(n * 2^n)	实现简单，思路清晰	时间复杂度高
动态规划 + 回溯	O(n * 2^n)	O(n * 2^n)	可以提前判断是否有解	实现稍复杂
纯回溯	O(n^n)	O(n)	空间复杂度低	时间复杂度极高，会超时

题目描述

难度

题目链接

示例

示例 1：

示例 2：

示例 3：

提示

解题思路

方法一：回溯 + 记忆化搜索

方法二：动态规划 + 回溯

图解思路

记忆化搜索分析表

回溯过程分析表

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目