题目重点：无空格字符串只用词典词切分，找一条可行句子或返回 None；用后缀可达 DP 记录选择并分析歧义。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版把‘有意义’限定为每段都在给定词典中，不使用外部语言模型评价语义。
- 任意一条合法切分即可；为确定性，代码按词的字典序选择第一条可延伸到结尾的路径。
- 词典空串被忽略，避免无限零长度转移；输入空串返回空句子，题目未明确该边界。
解题路线
- 令 reachable[i] 表示 text[i:] 能否完全由词典词切分，终点 reachable[n]=True。
- 从右到左，对每个 i 枚举词典词 w，若 text 在 i 开始匹配 w 且 reachable[i+|w|] 为真，就记录 choice[i]=w。
- reachable[0] 假则返回 None；否则按 choice 从 0 逐段前进并用空格拼接。
- 只存一个选择，不枚举所有句子；若词典大或文本长，可用 Trie 从每个 i 向前扫描，减少不匹配词的重复比较。
手动走一遍
text='applepie'、词典 {apple,pie}，从尾部先确定 pie 可达，再确定 apple 可接 pie，返回 'apple pie'。若 text='catsanddog' 且词典含 cat/cats/and/sand/dog，会有多种合法切分，训练版按词典字典序选一条。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections.abc import Iterable
def reconstruct_sentence(text: str, dictionary: Iterable[str]) -> str | None:
"""Return one segmentation, preferring lexicographically first word at each step."""
words = sorted({word for word in dictionary if word})
n = len(text)
choice: list[str | None] = [None] * (n + 1)
reachable = [False] * (n + 1)
reachable[n] = True
for i in range(n - 1, -1, -1):
for word in words:
end = i + len(word)
if end <= n and text.startswith(word, i) and reachable[end]:
reachable[i] = True
choice[i] = word
break
if not reachable[0]:
return None
output = []
i = 0
while i < n:
word = choice[i]
output.append(word)
i += len(word)
return ' '.join(output)
if __name__ == '__main__':
assert reconstruct_sentence('applepie', ['apple', 'pie']) == 'apple pie'
复杂度
字符串长 n、词典 W 个词、词长总和 S，朴素逐位置尝试所有词并比较最多 O(nS) 字符时间；reachable/choice O(n) 空间，加词典排序和结果。Trie 可把候选扫描限制在每个位置的最长可匹配深度，但输出仍 O(n)。
易错点与追问
容易失分的边界
- 只做布尔 Word Break，无法还原空格位置。
- 贪心选当前位置最长/最短词但未检查剩余后缀可达。
- 允许空词形成不前进的循环。
- 把语义‘有意义’自行引入模型评分，超出题目可核的字典约束。
继续深挖
- 若要返回全部有效句子，输出数量可能指数级，如何 memo？
- 若希望最少词数或最高词频分数，DP 状态和比较规则怎样改？
- 词典很大时 Trie 怎样减少扫描？
