题目描述
给定一个词典和一个不含空格的字符串，编写方法返回一个正确插入空格的字符串，使每个单词都在词典中。
示例
输入:
字符串: "bloombergisfun"
词典: ["bloom", "bloomberg", "is", "fun"]
输出: "bloomberg is fun"
解题思路
这是经典的 Word Break 问题，可以用多种方法解决：
方法一：贪心（最长匹配优先）
对于简单场景，贪心选择最长匹配的单词：
def word_break_greedy(s: str, word_dict: set) -> str:
result = []
i = 0
while i < len(s):
# 尝试匹配最长的单词
matched = False
for j in range(len(s), i, -1):
word = s[i:j]
if word in word_dict:
result.append(word)
i = j
matched = True
break
if not matched:
return "" # 无法切分
return ' '.join(result)
方法二：动态规划 + 回溯（推荐）
先用 DP 确认是否可切分，再用回溯构造结果：
def word_break(s: str, word_dict: list) -> str:
word_set = set(word_dict)
n = len(s)
# dp[i] 表示 s[0:i] 是否可以被切分
dp = [False] * (n + 1)
dp[0] = True
# parent[i] 记录从哪个位置跳转到 i
parent = [-1] * (n + 1)
for i in range(1, n + 1):
for j in range(i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
parent[i] = j
break # 找到一个即可
if not dp[n]:
return ""
# 回溯构造结果
words = []
i = n
while i > 0:
j = parent[i]
words.append(s[j:i])
i = j
return ' '.join(reversed(words))
方法三：返回所有可能的切分
如果有多种切分方式，返回所有结果：
def word_break_all(s: str, word_dict: list) -> list:
word_set = set(word_dict)
memo = {}
def dfs(start: int) -> list:
if start == len(s):
return [[]]
if start in memo:
return memo[start]
result = []
for end in range(start + 1, len(s) + 1):
word = s[start:end]
if word in word_set:
for rest in dfs(end):
result.append([word] + rest)
memo[start] = result
return result
return [' '.join(words) for words in dfs(0)]
# 示例
print(word_break_all("bloombergisfun", ["bloom", "bloomberg", "is", "fun"]))
# 输出: ["bloom berg is fun", "bloomberg is fun"] 或类似
复杂度分析
- 贪心：O(n²) 时间，O(n) 空间
- DP：O(n² × L) 时间，O(n) 空间，L 是最长单词长度
- 返回所有结果：最坏 O(2^n)，因为可能有指数级结果
面试要点
- 确认输出格式：返回一个还是所有切分方式
- 无法切分的处理：返回空字符串还是抛异常
- 大小写敏感：是否需要忽略大小写
需要面试辅助服务？联系我们
- 📧 Email: [email protected]
- 📱 Phone: +86 17863968105
需要面试真题？ 立刻联系微信 Coding0201，获得真题。