题目重点：以可达前缀为DP状态，在Trie内探索所有词结尾，解释最长词贪心失败、空词和结果输出。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 按顺序覆盖整个目标字符串，不重排字符；词典词可重复，空词忽略，重复词去重。
- 空目标字符串按零个词拼接返回True；比较按code point、区分大小写。
- 返回布尔结果，不列出所有句子；列举版的输出规模可指数增长。
解题路线
- 令reachable[i]表示前i个字符已经能完整分词。reachable[0]=True，只有已可达位置才发起下一个词匹配；不存在的前缀不能因为局部匹配了单词就转True。
- 把词典建Trie，从每个可达i沿text[i:]前进，遇终止标记就把对应j+1设True；继续走，因为短词和长词都可能是有效下一步。
- 贪心选最长词不可靠：text=abcdef、词典[abcd,abc,def]，先abcd会卡在ef，但abc+def成功。DP保留所有可达结尾而非选一个最长匹配。
- 正确性按前缀长度归纳：每次转移来自可分前缀和一个词典词，产生合法拼接；任意合法完整拼接最后一词的开始前缀必可达，该词沿Trie会被走到，所以不会漏。
- 词典空词若用朴素递归可能形成不推进位置的循环；本文直接忽略，不改变布尔可分性。terminal用私有object，避免真实字符和特殊字符串标签冲突。
- 复杂度还要考虑实现细节：若反复切text[i:j]再哈希，构造/哈希字符串会引入额外字符成本。Trie按字符走可避免这些切片，但每个可达位置仍可能走到最长词长度。
- 需要一组分词时记录首次成功前驱；需要所有分词时DP只帮判可达，再回溯输出，答案数本身不可忽略。流式输入若词长度有上限可做窗口状态，但全文词典匹配合同要保持。
手动走一遍
catsanddog可用cats+and+dog，也可cat+sand+dog，只问布尔时均证明True。aaaa与词典[aa]可重复两次，不能因词典仅一个aa就返回False。abcdef的长词贪心例说明不能只接受一个路径。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Boolean segmentation with reusable nonempty dictionary words.
Empty text is segmentable; empty words ignored, duplicate words deduplicated.
"""
def can_segment(text, words):
root = {}
terminal = object()
for word in set(words):
if not word:
continue
node = root
for char in word:
node = node.setdefault(char, {})
node[terminal] = True
reachable = [False] * (len(text) + 1)
reachable[0] = True
for i in range(len(text)):
if not reachable[i]:
continue
node = root
for j in range(i, len(text)):
if text[j] not in node:
break
node = node[text[j]]
if terminal in node:
reachable[j + 1] = True
return reachable[-1]
复杂度
设词典总字符S、最长词长L、目标长n，建Trie期望O(S)，DP遍历O(n·min(n,L))最坏时间，空间O(S+n)。输出所有拆分时再加答案构建成本。
易错点与追问
容易失分的边界
- 词典可复用却把用过词删除。
- 最长匹配贪心。
- 空词导致无限递归。
- 声称哈希子串是免费O(1)。
继续深挖
- 如何返回一组拆分或最少词数？
- 能否计数且对大数取模？
- 大小写/Unicode归一化在哪一步做？
- 词典频繁变化如何复用索引？
