连接词

笨办法是枚举所有切法、看每段是不是词——切法呈指数级爆炸。但「能拼到这里」是可以一段一段攒出来的，这正是动态规划的味道。

dp[0]=真(空串天然拼好，作地基)。要算 dp[i]，就找一个切点 j：若 dp[j] 为真 且 子串 word[j:i] 在词表里，那 dp[i] 也为真。我们拿 catsdog 一格一格演给你看。

判断 catsdog 时，词表里虽然也有 catsdog，但这一段必须排除自己，逼着它真去用 cats、dog 这些更短的别的词拼。下面填表时这条会自动满足。

候选词 catsdog · 字典就在右边：下面这排是候选词 catsdog 的 7 个字符。右边是可用的积木词。我们要从左往右，问「前 1 个、前 2 个…前 7 个字符能不能拼出来」。

建 dp 行 · dp[i]=前 i 字符可拼否：上一行写出「前 i 个字符」长什么样，下一行是要填的 dp。dp[7] 对应整个 catsdog——它若为真，catsdog 就是连接词。开始填。

地基 · dp[0]=真：地基 dp[0]=真：前 0 个字符是空串，天然成立。所有切分都从某个「为真的 dp[j]」往后接，这就是起跳点。

填 dp[1] · 前缀 c：算 dp[1]：从为真的 dp[0] 起跳，看子串 word[0:1]="c"。词表里没有 "c"，拼不出 → dp[1]=假。

填 dp[2] · 前缀 ca：算 dp[2]：从 dp[0] 起跳看 "ca"，不在词表；从 dp[1] 起跳但 dp[1] 是假、没法接。两条路都断 → dp[2]=假。

填 dp[3] · 先试切点 j=0：算 dp[3] 时，内层指针 j 从 0 开始扫。先落在为真的 dp[0]，截取它到位置 3 之间的子串 word[0:3]，下一帧看它在不在词表。

填 dp[3] · 前缀 cat · 第一次命中：算 dp[3]：从为真的 dp[0] 起跳，子串 word[0:3]="cat" 正好在词表里！前 3 个字符能拼出 → dp[3]=真。第一个真出现了。

填 dp[4] · 先试切点 j=3：算 dp[4]，先就近从真格 dp[3](cat)起跳，剩 word[3:4]="s" 不是词。别急，还能从最早的 dp[0] 起跳取一整段。

填 dp[4] · 前缀 cats · 再命中：算 dp[4]：从 dp[0] 起跳，word[0:4]="cats" 也在词表！于是 dp[4]=真。注意 dp[3](cat)也真，但从 dp[3] 起跳的 "s" 不是词，靠的是 cats 这一整段。

填 dp[5] · 试切点 j=3：算 dp[5]，先从真格 dp[3](已拼好 cat)起跳，剩下 word[3:5]="sd"——不是词。这个落脚点不行，再试下一个真格 dp[4]。

填 dp[5] · 前缀 catsd：算 dp[5]：能起跳的真格是 dp[3]、dp[4]。从 dp[3] 看 "sd"、从 dp[4] 看 "d"，都不是词。前 5 个字符拼不出 → dp[5]=假。

填 dp[6] · 试切点 j=4：算 dp[6]，从真格 dp[4](cats)起跳，剩 word[4:6]="do"——还差一个字母，不是词。从 dp[3] 起跳的 "sdo" 也不是。

填 dp[6] · 前缀 catsdo：两个落脚点 dp[3]、dp[4] 都试过，得到 "sdo"、"do" 都不是词 → dp[6]=假。差一个字母 g 就成 dog 了，再走最后一格。

复盘 · 哪些 dp 格是「落脚点」：填到这里，真格(绿)只有 dp[0]、dp[3]、dp[4]——它们是仅有的「落脚点」。算最后的 dp[7] 时，只能从这几格往后接一个词。下面逐个试。

填 dp[7] · 先试切点 j=3：算 dp[7]，先从真格 dp[3](已拼好 cat)起跳，剩下 word[3:7]="sdog"——不是词，这个切点不行。别急，还有 dp[4] 可以试。

填 dp[7] · 整词 · 收官命中：算 dp[7]：从为真的 dp[4](对应已拼好的 cats)起跳，剩下 word[4:7]="dog" 正好是词！于是 dp[7]=真——catsdog = cats + dog，两段都是别的词。

回看切分 · cats | dog：把命中路径标出来：前 4 个字符 "cats" 是一段词，后 3 个 "dog" 是另一段词。两段拼起来正好是 catsdog，用了两个别的词——这就是连接词的定义。

填表完成 · catsdog 是连接词：dp 行最后一格 dp[7]=真，且拼它用的是 cats、dog 两个别的词(没用自己)，满足「至少两个词」。catsdog 确认是连接词，加入答案。

其它三个词都拆不出：把四个词各自跑一遍 DP(判自己时排除自己)：cat、cats、dog 都太短、拆不出别的词，只有 catsdog 命中。所以答案就是 [catsdog]。

对长度 L 的词，dp 有 L 个位置、每个位置回看 ≤L 个切点，子串查词表近 O(1)，单词 O(L²)；所有词总长 N，整体约 O(N·L)。比指数枚举快到天上。

雷区实演 · 没排除自己：若不排除自己，算 dp[7] 时从 dp[0] 起跳、子串恰是整个 catsdog、也在词表里——dp[7] 照样为真，可这是「一段就是它本身」，根本没拆开。所以必须跳过 sub==word 这种情况。

边界三连：注意空串：它会让 dp[0] 的地基和「整词」重合，必须在入口处直接判掉，否则空串会被误当成连接词。

面试追问：把「它就是对每个词跑一遍单词拆分」一句话讲透，再补「排序+短词字典」的优化和 Trie 选项，是这题的加分点。