Hard

题目描述

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

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

示例 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 中所有字符串都 不同
  • 输入保证答案的长度不超过 10^5

解题思路

这道题要求找出所有可能的单词拆分方案，是经典的回溯算法问题。

核心思路：

  1. 使用回溯法遍历所有可能的拆分方案
  2. 从字符串的每个位置开始，尝试匹配字典中的所有单词
  3. 如果找到匹配的单词，递归处理剩余部分
  4. 使用记忆化优化，避免重复计算相同子问题

优化策略：

  • 将字典转换为哈希集合，提高查找效率
  • 使用记忆化存储每个位置开始的所有可能拆分结果
  • 预先检查是否可能拆分（可选优化）

算法流程：

  1. 将 wordDict 转换为集合便于快速查找
  2. 定义递归函数，从当前位置开始寻找所有可能的拆分
  3. 遍历所有可能的单词长度，检查是否在字典中
  4. 如果找到匹配单词，递归处理剩余部分并组合结果
  5. 使用记忆化缓存避免重复计算

代码实现

class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict(wordDict.begin(), wordDict.end());
        unordered_map<int, vector<string>> memo;
        return backtrack(s, 0, dict, memo);
    }
    
private:
    vector<string> backtrack(const string& s, int start, 
                           const unordered_set<string>& dict,
                           unordered_map<int, vector<string>>& memo) {
        if (memo.find(start) != memo.end()) {
            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 (dict.count(word)) {
                vector<string> sublist = backtrack(s, end, dict, memo);
                for (const string& sub : sublist) {
                    result.push_back(word + (sub.empty() ? "" : " " + sub));
                }
            }
        }
        
        memo[start] = result;
        return result;
    }
};

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        word_set = set(wordDict)
        memo = {}
        
        def backtrack(start):
            if start in memo:
                return memo[start]
            
            if start == len(s):
                return [""]
            
            result = []
            for end in range(start + 1, len(s) + 1):
                word = s[start:end]
                if word in word_set:
                    sublist = backtrack(end)
                    for sub in sublist:
                        result.append(word + ("" if not sub else " " + sub))
            
            memo[start] = result
            return result
        
        return backtrack(0)

public class Solution {
    public IList<string> WordBreak(string s, IList<string> wordDict) {
        HashSet<string> dict = new HashSet<string>(wordDict);
        Dictionary<int, IList<string>> memo = new Dictionary<int, IList<string>>();
        return Backtrack(s, 0, dict, memo);
    }
    
    private IList<string> Backtrack(string s, int start, HashSet<string> dict, Dictionary<int, IList<string>> memo) {
        if (memo.ContainsKey(start)) {
            return memo[start];
        }
        
        IList<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 (dict.Contains(word)) {
                IList<string> sublist = Backtrack(s, end, dict, memo);
                foreach (string sub in sublist) {
                    result.Add(word + (string.IsNullOrEmpty(sub) ? "" : " " + sub));
                }
            }
        }
        
        memo[start] = result;
        return result;
    }
}

var wordBreak = function(s, wordDict) {
    const wordSet = new Set(wordDict);
    const memo = new Map();
    
    function backtrack(start) {
        if (start === s.length) {
            return [[]];
        }
        
        if (memo.has(start)) {
            return memo.get(start);
        }
        
        const result = [];
        
        for (let end = start + 1; end <= s.length; end++) {
            const word = s.substring(start, end);
            
            if (wordSet.has(word)) {
                const suffixes = backtrack(end);
                for (const suffix of suffixes) {
                    result.push([word, ...suffix]);
                }
            }
        }
        
        memo.set(start, result);
        return result;
    }
    
    const sentences = backtrack(0);
    return sentences.map(sentence => sentence.join(' '));
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(2^n * n)，其中 n 是字符串长度。最坏情况下需要尝试所有可能的拆分方案，每个位置都可能是拆分点
空间复杂度O(2^n * n)，记忆化存储和递归调用栈的空间消耗，以及存储所有可能结果的空间

相关题目