连接词 图解题解

这道题到底在问什么

words

["cat","cats","dog","catsdog"]

输出

["catsdog"]

解释

catsdog = cats + dog，两个都在词表里；其余三个拆不出

先想最直接的笨办法

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

最优解：一步一步想明白

1. 3笨办法是枚举所有切法、看每段是不是词——切法呈指数级爆炸。但「能拼到这里」是可以一段一段攒出来的，这正是动态规划的味道。
2. 4dp[0]=真(空串天然拼好，作地基)。要算 dp[i]，就找一个切点 j：若 dp[j] 为真 且 子串 word[j:i] 在词表里，那 dp[i] 也为真。我们拿 catsdog 一格一格演给你看。
3. 5判断 catsdog 时，词表里虽然也有 catsdog，但这一段必须排除自己，逼着它真去用 cats、dog 这些更短的别的词拼。下面填表时这条会自动满足。
4. 6逐字符摆开，准备做单词拆分下面这排是候选词 catsdog 的 7 个字符。右边是可用的积木词。我们要从左往右，问「前 1 个、前 2 个…前 7 个字符能不能拼出来」。
5. 7dp 长度 = 字符数+1 = 8上一行写出「前 i 个字符」长什么样，下一行是要填的 dp。dp[7] 对应整个 catsdog——它若为真，catsdog 就是连接词。开始填。
6. 8空串天然拼好地基 dp[0]=真：前 0 个字符是空串，天然成立。所有切分都从某个「为真的 dp[j]」往后接，这就是起跳点。
7. 9唯一切点 j=0：子串 c 不在词表算 dp[1]：从为真的 dp[0] 起跳，看子串 word[0:1]="c"。词表里没有 "c"，拼不出 → dp[1]=假。
8. 10试切点 j=0：子串 ca 不在词表算 dp[2]：从 dp[0] 起跳看 "ca"，不在词表；从 dp[1] 起跳但 dp[1] 是假、没法接。两条路都断 → dp[2]=假。
9. 11扫到 j=0：取子串 word[0:3]算 dp[3] 时，内层指针 j 从 0 开始扫。先落在为真的 dp[0]，截取它到位置 3 之间的子串 word[0:3]，下一帧看它在不在词表。
10. 12切点 j=0：子串 cat 在词表！算 dp[3]：从为真的 dp[0] 起跳，子串 word[0:3]="cat" 正好在词表里！前 3 个字符能拼出 → dp[3]=真。第一个真出现了。
11. 13dp[3]真，看子串 s算 dp[4]，先就近从真格 dp[3](cat)起跳，剩 word[3:4]="s" 不是词。别急，还能从最早的 dp[0] 起跳取一整段。
12. 14切点 j=0：子串 cats 在词表！算 dp[4]：从 dp[0] 起跳，word[0:4]="cats" 也在词表！于是 dp[4]=真。注意 dp[3](cat)也真，但从 dp[3] 起跳的 "s" 不是词，靠的是 cats 这一整段。
13. 15dp[3]真，看子串 sd算 dp[5]，先从真格 dp[3](已拼好 cat)起跳，剩下 word[3:5]="sd"——不是词。这个落脚点不行，再试下一个真格 dp[4]。
14. 16再试 dp[4]：子串 d 也不在词表算 dp[5]：能起跳的真格是 dp[3]、dp[4]。从 dp[3] 看 "sd"、从 dp[4] 看 "d"，都不是词。前 5 个字符拼不出 → dp[5]=假。
15. 17dp[4]真，看子串 do算 dp[6]，从真格 dp[4](cats)起跳，剩 word[4:6]="do"——还差一个字母，不是词。从 dp[3] 起跳的 "sdo" 也不是。
16. 18所有切点都不成立两个落脚点 dp[3]、dp[4] 都试过，得到 "sdo"、"do" 都不是词 → dp[6]=假。差一个字母 g 就成 dog 了，再走最后一格。
17. 19只有真格 dp0/dp3/dp4 能起跳填到这里，真格(绿)只有 dp[0]、dp[3]、dp[4]——它们是仅有的「落脚点」。算最后的 dp[7] 时，只能从这几格往后接一个词。下面逐个试。
18. 20dp[3]真，但子串 sdog 不在词表算 dp[7]，先从真格 dp[3](已拼好 cat)起跳，剩下 word[3:7]="sdog"——不是词，这个切点不行。别急，还有 dp[4] 可以试。
19. 21切点 j=4：dp[4]真 且 dog 在词表！算 dp[7]：从为真的 dp[4](对应已拼好的 cats)起跳，剩下 word[4:7]="dog" 正好是词！于是 dp[7]=真——catsdog = cats + dog，两段都是别的词。
20. 22命中路径：dp[0]→dp[4]→dp[7]把命中路径标出来：前 4 个字符 "cats" 是一段词，后 3 个 "dog" 是另一段词。两段拼起来正好是 catsdog，用了两个别的词——这就是连接词的定义。
21. 23答案 dp[7]=真dp 行最后一格 dp[7]=真，且拼它用的是 cats、dog 两个别的词(没用自己)，满足「至少两个词」。catsdog 确认是连接词，加入答案。
22. 24cat/cats/dog 各自 dp[末尾]=假把四个词各自跑一遍 DP(判自己时排除自己)：cat、cats、dog 都太短、拆不出别的词，只有 catsdog 命中。所以答案就是 [catsdog]。
23. 25对长度 L 的词，dp 有 L 个位置、每个位置回看 ≤L 个切点，子串查词表近 O(1)，单词 O(L²)；所有词总长 N，整体约 O(N·L)。比指数枚举快到天上。
24. 29误用整段 catsdog 自己若不排除自己，算 dp[7] 时从 dp[0] 起跳、子串恰是整个 catsdog、也在词表里——dp[7] 照样为真，可这是「一段就是它本身」，根本没拆开。所以必须跳过 sub==word 这种情况。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def findAllConcatenatedWordsInADict(self, words):
        wordset = set(words)
        def canForm(word):
            if not word:
                return False
            n = len(word)
            dp = [False] * (n + 1)
            dp[0] = True                 # 空串地基
            for i in range(1, n + 1):
                for j in range(0, i):
                    if not dp[j]:
                        continue
                    sub = word[j:i]
                    if sub == word:      # 不能用自己
                        continue
                    if sub in wordset:
                        dp[i] = True
                        break
            return dp[n]
        return [w for w in words if canForm(w)]

class Solution {
public:
    unordered_set<string> wordset;
    bool canForm(const string& word) {
        int n = word.size();
        if (n == 0) return false;
        vector<bool> dp(n + 1, false);
        dp[0] = true;                       // 空串地基
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (!dp[j]) continue;
                string sub = word.substr(j, i - j);
                if (sub == word) continue;      // 不能用自己
                if (wordset.count(sub)) { dp[i] = true; break; }
            }
        }
        return dp[n];
    }
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        for (const string& w : words) wordset.insert(w);
        vector<string> res;
        for (const string& w : words)
            if (canForm(w)) res.push_back(w);
        return res;
    }
};

class Solution {
    private Set<String> wordset = new HashSet<>();
    private boolean canForm(String word) {
        int n = word.length();
        if (n == 0) return false;
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;                       // 空串地基
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (!dp[j]) continue;
                String sub = word.substring(j, i);
                if (sub.equals(word)) continue; // 不能用自己
                if (wordset.contains(sub)) { dp[i] = true; break; }
            }
        }
        return dp[n];
    }
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        for (String w : words) wordset.add(w);
        List<String> res = new ArrayList<>();
        for (String w : words)
            if (canForm(w)) res.add(w);
        return res;
    }
}

复杂度

面试官可能追问