leetcode_字典树140.单词拆分II

140. 单词拆分 II

给定一个字符串 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”]

输出:[]

思路:

递归函数设计：

定义一个递归函数 backtrack(s, path, result)，其中 s 是当前待处理的字符串，path是当前已经分割好的单词列表，result是最终的结果列表

如果 s 为空，说明我们已经成功分割了整个字符串，将path中的单词用空格连接起来，加入result中

否则，遍历 s 的所有可能的前缀，如果某个前缀在wordDict中，就递归处理剩下的字符串，并将当前前缀加入path中

优化：

为了避免重复计算，可以使用记忆化技术（Memoization）来存储已经处理过的子串的结果

class Solution(object): def wordBreak(self, s, wordDict): """ :type s: str :type wordDict: List[str] :rtype: List[str] """ wordDict = set(wordDict) # 转换为集合，方便快速查找 memo = {} # 用于记忆化 def backtrack(s): if s in memo: return memo[s] if not s: return [""] # 返回一个包含空字符串的列表，表示成功分割 result = [] for i in range(1, len(s) + 1): word = s[:i] if word in wordDict: for sentence in backtrack(s[i:]): if sentence: result.append(word + " " + sentence) else: result.append(word) memo[s] = result return result return backtrack(s) 执行流程示例 开始: "catsanddog" | ├── 分割 "cat" -> 剩下 "sanddog" | | | └── 分割 "sand" -> 剩下 "dog" | | | └── 分割 "dog" -> 剩下 "" | | | └── 成功分割: "cat sand dog" | └── 分割 "cats" -> 剩下 "anddog" | └── 分割 "and" -> 剩下 "dog" | └── 分割 "dog" -> 剩下 "" | └── 成功分割: "cats and dog"

时间复杂度：最坏情况下，每个子串都需要被处理一次，时间复杂度为 O(2^n)，但由于使用了记忆化，实际复杂度会降低

空间复杂度：主要是递归栈和记忆化存储的空间，最坏情况下为 O(n^2)