题目重点：按字符位置做分词DP，排除直接用自己一次的平凡答案，并核对重复词与空串。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练返回输入中能由至少2个非空字典词拼成的不同词，保持首次输入顺序；至少2是标准训练防平凡合同，正式题仍待核。
- 允许重复使用同一词，不要求每个输入位置最多使用一次；空词忽略，避免零长度递归。
解题路线
- 对每个目标word，best[i]记录前i个字符最多可切几块，-1代表不可达，best[0]=0。转移从所有start<end检查word[start:end]是否在dictionary。
- 每次合法转移增加一块，目标best[len]≥2才输出；字典包含目标本身只产生1块，不足通过。保留“最大块数”而不是简单布尔可达使至少2要求可验证。
- 位置递增构成DAG，同一词可以反复使用，不需要全局visited words；若用visited词名会错拒绝catcat。DFS也应memo按位置/合同状态，而不是禁止词复用。
- 正确性由最后一块切点枚举：每个合法分词都有最后start，前缀可达加字典片段生成它；每个DP转移又构成一个合法分词，所以最大块数精确。
- Python切片与hash不是O(1)：每个候选片段要复制/哈希字符，基线最坏O(L³)。Trie从每start前进字符可把枚举工作约降O(L²)，仍要明确不同词目标总成本。
手动走一遍
训练[cat,dog,catcat,catsdog]只能输出catcat，因cat复用两次，catsdog缺cats；加cats后catsdog也输出。空串不能作为无限零长度片段。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def concatenated_words(words):
"""Return distinct input words formed by >=2 nonempty dictionary pieces, reuse allowed."""
dictionary=set(words)-{''}
output=[]
seen=set()
for word in words:
if not word or word in seen:continue
seen.add(word)
best=[-1]*(len(word)+1)
best[0]=0
for end in range(1,len(word)+1):
for start in range(end):
if best[start]>=0 and word[start:end] in dictionary:
best[end]=max(best[end],best[start]+1)
if best[-1]>=2:output.append(word)
return output
复杂度
每目标长L，Python切片基线最坏O(L³)时间、O(L)DP状态另加输入字典；全输入按ΣL_i³计算，不声称DFS天然线性。
易错点与追问
容易失分的边界
- word在字典就直接接受自己一块。
- visited词禁止合法复用。
- 空词导致递归不前进。
- 切片成本隐藏成O(1)。
继续深挖
- 只问给定目标是否可拼怎样改？
- 要返回分词路径怎么加prev？
- 正式题若允许一块，答案为何变得平凡？
