某程序员:高杠杆生活太可怕了!同事被裁赔偿了30万，大家都以为他会开心，但他深圳房贷每月就有3万，30万也撑不了多久

刚刷到这个帖子，我第一反应不是30万好多，是这点钱放深圳房贷面前，真跟往火里扔一杯水差不多。

大家老觉得被裁拿赔偿像中个小奖，能歇口气，结果人家一个月月供就3万，30万听着挺唬人，实际也就撑几个月，连发呆都不敢发太久。

高杠杆这事平时看着风光，真出点波动，人立马就麻了。你说他能不焦虑吗，工作没了，房贷还在那儿，银行又不会因为你被裁就跟你讲感情。最扎心的是，旁边人还会来一句“不是赔了30万吗”，这话一出来，估计本人只能苦笑。

有些字符串题，第一眼看着像字典匹配，真下手一写就开始乱。

catdog 是不是连接词？catcatdog 呢？再坏一点，字典里本身就有 catdog，你到底是把它当成一个完整单词，还是拆成 cat + dog？这种题我一般不急着上回溯。回溯能写，但很容易写成“逮着一个前缀就往下冲”，数据一大就开始抖。像这种“一个词能不能由别的词拼出来”的判断，先把顺序理对，比代码技巧更重要。这个写法我刻意按现场解题的味道来收，不走教材腔，风格上也参考了你给的几篇技术文那种“先落问题，再给判断”的劲儿。

这道“连接词”，核心不是找两个词拼一下就完了，而是判断一个单词能不能由词典中至少两个更短的词组成。

我习惯这么处理：

先把所有单词按长度从小到大排序。为什么？因为当前单词要不要被认成连接词，依赖的是前面那些更短的词。短词先入池，长词后判断，思路会很顺。这里我第一眼就不太信那种“把所有词一次性放进集合里，然后递归硬拆”的写法，因为它很容易把自己也拿来拼自己，边界一多就开始打补丁。

判断某个词 word 时，用动态规划。

dp[i] 表示前 i 个字符能不能被词典里的单词拼出来。 转移也不复杂：枚举切分点 j，如果 dp[j] 为真，并且 word[j:i] 在已有词典里，那 dp[i] = True。

这个过程跟“单词拆分”很像，但有个细节不能丢：当前词不能先放进集合再判断。不然 catsdog 这种词，可能被自己误伤成可拆分。

代码我自己按这个思路写了一版，没走那种网上常见的模板味：

from typing import List


classSolution:
deffindAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        words.sort(key=len)
        built = set()
        ans = []

for word in words:
ifnot word:
continue

if self._can_build(word, built):
                ans.append(word)

            built.add(word)

return ans

def_can_build(self, word: str, built: set[str]) -> bool:
ifnot built:
returnFalse

        n = len(word)
        dp = [False] * (n + 1)
        dp[0] = True

for i in range(1, n + 1):
for j in range(i):
ifnot dp[j]:
continue
                piece = word[j:i]
if piece in built:
                    dp[i] = True
break

return dp[n]

拿这组数据跑一下：

words = ["cat", "cats", "dog", "catsdog", "dogcat", "rat", "ratcatdogcat"]

print(Solution().findAllConcatenatedWordsInADict(words))
# ['dogcat', 'catsdog', 'ratcatdogcat']

这个写法有两个地方比较稳。

一个是排序。短词天然先构成“材料库”，后面的长词只负责判断，不会乱。

另一个是 built 集合查询快。DP 里最烦的不是状态定义，是真跑起来切片和查找次数很多。集合查单词，至少不会在“词典里有没有这段”上额外浪费时间。

当然，这题还能继续抠性能。比如内层枚举 j 的时候，其实可以结合词典里的最长单词长度做剪枝，没必要每次都从 0 扫到 i。但面试里先把主干写稳更重要，别一上来就优化，最后把自己绕进去。

再说一下复杂度。假设单词平均长度是 L，单词数量是 N，那整体大致是 O(N * L^2)。因为每个单词都要做一遍 DP，而一遍 DP 里有双层切分判断。这个复杂度不算惊艳，但对这题是够用的，而且代码干净，边界也少。