LeetCode 题解工作台
单词拆分 II
给定一个字符串 s 和一个字符串字典 wordDict ，在字符串 s 中增加空格来构建一个句子，使得句子中所有的单词都在词典中。 以任意顺序 返回所有这些可能的句子。 注意： 词典中的同一个单词可能在分段中被重复使用多次。 示例 1： 输入: s = "catsanddog", wordDict …
7
题型
4
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
class Trie: def __init__(self):
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给定一个字符串 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 <= 201 <= wordDict.length <= 10001 <= wordDict[i].length <= 10s和wordDict[i]仅有小写英文字母组成wordDict中所有字符串都 不同
解题思路
方法一：前缀树 + DFS
class Trie:
def __init__(self):
self.children = [None] * 26
self.is_end = False
def insert(self, word):
node = self
for c in word:
idx = ord(c) - ord('a')
if node.children[idx] is None:
node.children[idx] = Trie()
node = node.children[idx]
node.is_end = True
def search(self, word):
node = self
for c in word:
idx = ord(c) - ord('a')
if node.children[idx] is None:
return False
node = node.children[idx]
return node.is_end
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
def dfs(s):
if not s:
return [[]]
res = []
for i in range(1, len(s) + 1):
if trie.search(s[:i]):
for v in dfs(s[i:]):
res.append([s[:i]] + v)
return res
trie = Trie()
for w in wordDict:
trie.insert(w)
ans = dfs(s)
return [' '.join(v) for v in ans]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n \cdot 2^n) |
| 空间 | O(n \cdot 2^n) |
面试官常问的追问
外企场景- question_mark
Do you understand how dynamic programming and backtracking work together in this problem?
- question_mark
Can you explain why memoization significantly improves the efficiency of this solution?
- question_mark
Will you be able to identify the pattern in an input string and apply the array scanning approach with hash lookup?
常见陷阱
外企场景- error
Failing to handle substrings that are not valid words in the dictionary.
- error
Overlooking memoization which may lead to recalculating the same substrings repeatedly, slowing down the solution.
- error
Not considering the case where no valid sentence exists and returning an empty result when necessary.
进阶变体
外企场景- arrow_right_alt
Word Break I: Given the same problem without needing to return all possible sentences, just checking for a valid segmentation.
- arrow_right_alt
Word Break III: Given a string and dictionary, return the minimum number of spaces needed to split the string into valid words.
- arrow_right_alt
Word Break IV: Similar to Word Break II, but with additional constraints on the number of dictionary words allowed.