题目重点：字符串是否能由词典中的非空词重复拼接。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 按Unicode code point切分，词可多次使用；空目标True，空词从词典剔除不贡献进度。
- 只返回能否，不枚举全部分词。
解题路线
- dp[end]代表s[:end]能拼出。尝试词长上限M内的start，如果dp[start]且s[start:end]在词典，则为True。
- 该位置DAG只向更大end推进，因此按end从小到大即可。无memo回溯在多种重叠前缀上可能指数重复。
- 用Trie从每个可达start向右走，可避免每次切片/哈希成本，O(nM)字符访问；生成全部方案则输出数可指数大，需要另设上限。
手动走一遍
s=leetcode、words={leet,code}在end4/end8依次True。s=catsandog有cat/cats/sand/and/dog，但不能完成末段，不能只因每词在字符串中出现就True。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def word_break(s,words):
words=set(words)
if '' in words:words.remove('')
length=max(map(len,words),default=0)
dp=[True]+[False]*len(s)
for end in range(1,len(s)+1):
dp[end]=any(dp[start] and s[start:end] in words for start in range(max(0,end-length),end))
return dp[-1]
复杂度
Python基线最多O(nM)候选，但切片及hash有长度成本，保守O(nM²)时间；O(n+词典总长)空间。Trie可改善候选处理成本。
易错点与追问
容易失分的边界
- 只看词典最长词前缀贪心会漏掉短词可完成的方案。
- 空词递归若无进度会无限循环。
继续深挖
- 返回一个分词，怎样保存parent start？
- 每个词有代价，最少总成本递推怎样改？
