LeetCode 472. 连接词

2022-01-01 HGNULB 约 13 分钟

文章信息 6 个分类 6 个标签

分类

题目描述

✅ 472. 连接词

题意分析

题目目标：给定一个不含重复项的单词列表，找出其中所有的「连接词」并返回。连接词的定义是：这个单词完全由列表中至少两个更短的单词拼接而成。
核心约束：「至少两个」这四个字是全部题眼——每个单词本身也在词典里，如果不加限制，任何单词都能被自己「拼」出来，答案就变成了整个列表。因此判定过程中必须显式地记录用了几个片段，或者在查询时把自身排除。第二个信号是「拼接而成」意味着这是一道单词拆分问题，只不过词典和待拆单词来自同一个集合。第三个是数据规模：单词数可达 $10^4$、总字符数可达 $10^5$，对每个单词做一次朴素的拆分判定需要在词典里反复查前缀，如果每次都遍历整个词典就是 $10^8$ 量级，必须用能按字符逐步推进的结构来加速前缀查询。
边界处理：列表中可能含有空字符串，它既不该被插入词典（否则任何位置都能「匹配」出一个空片段导致死循环），也不该出现在答案里；单个字母的单词不可能是连接词，但不需要特判，判定逻辑自然会排除；拆分方案可能有多种，只要存在一种合法方案就应计入答案；同一个起始位置可能被多条不同的拆分路径重复访问，需要缓存避免指数级重复计算。

解法：字典树 + DFS 计数

核心思路

最朴素的写法是对每个单词做一遍「单词拆分」式的动态规划：dp[i] 表示前 i 个字符能否被拆成词典中的单词，转移时枚举上一个断点 j 并判断 word[j..i) 是否在词典里。用哈希集合存词典的话，单个单词的判定是 $O(L^2)$ 次子串截取与哈希查询，而每次截取本身还要 $O(L)$ 的拷贝，总代价在 $10^4$ 个单词、单词长度可观时非常吃紧。瓶颈在于：枚举断点时反复截取子串再整体查询，浪费了「这些子串共享前缀」这一结构。
关键观察是：从某个起点出发向右延伸，word[idx..idx]、word[idx..idx+1]、word[idx..idx+2] 这一串候选片段是层层嵌套的前缀关系。字典树天生就是为这种查询设计的——沿着字符一步步下沉，每走一步就知道「当前走过的这段是不是一个完整单词」（看节点的结束标记），而且一旦某个字符在树上没有对应分支，就说明再往右延伸也不可能匹配上任何单词，可以立即停止。这样一趟下沉就把从某个起点出发的所有候选片段全部检查完了，代价只有 $O(L)$ 而非 $O(L^2)$。
于是先按长度升序处理单词：判定当前单词时，字典树只含已经处理过的单词；判定结束后再插入当前词，避免它用自身完成一次匹配。定义递归函数 dfs(idx, count)：从 idx 开始的后缀能否继续拆分，使总片段数不少于 2。递归到末尾时返回 count >= 2；按长度处理与片段计数共同保证连接词确实由至少两个更短单词组成。

自身排除发生在操作顺序上：必须“先判定、后插入”。输入单词互不重复，因此此前即使有等长单词，也不可能完整匹配当前词；任何真正参与拼接的片段都严格短于当前词。count >= 2 再对题目定义做一次显式校验。
由于同一个起点可能被多条路径反复到达（比如 "aaaa" 可以先切 "a" 再切 "a"，也可以先切 "aa"，两条路径都会走到下标 2），必须加记忆化。这里有个值得说清的细节：缓存只按 idx 建索引而不含 count，看起来会串味，实际不会——因为除了起点 idx = 0 之外，任何被递归到的位置都已经至少切出了一个片段，也就是 count 至少为 1，此时「能否走到末尾」与「总数是否达到 2」是等价的（再切一个就够 2 了）；而 idx = 0 对应的调用全局只发生一次，不存在被复用的风险。

解题步骤

第一步：按长度升序排序，逐个“先判定、后插入”字典树，空串直接跳过。 判定时当前词尚未入树，避免自匹配；字典树沿字符增量下沉，一次遍历即可覆盖同一起点的所有前缀候选。

第二步：对每个单词准备一个长度为 len + 1 的记忆化数组并填成 -1，表示尚未计算。 为什么每个单词要各开一份：缓存的语义绑定在「当前这个单词的某个下标」上，跨单词复用毫无意义且会给出错误结论。为什么用 -1 而不是布尔数组：需要区分「没算过」「算过且为真」「算过且为假」三种状态，单个布尔量表达不了。

第三步：调用 dfs(root, word, 0, 0, memo)，起始下标为 0、已切片段数为 0。 为什么初始 count 是 0：还没有切出任何片段，这个初值保证了「整词一次匹配」时走到末尾 count 只有 1，被出口条件正确否决。

第四步：递归入口先判 idx == word.length()，是则返回 count >= 2。 为什么这个判断要放在查缓存之前：末尾位置的结论依赖 count 而不依赖缓存，把它放在后面会让 memo[len] 被写入一个与 count 绑定的值，破坏缓存语义。

第五步：查缓存，命中直接返回。 为什么这是必须的：没有记忆化时，形如 "aaaa...a" 的输入会让切分路径呈指数级爆炸；有了缓存，每个起点最多被真正计算一次。

第六步：从根节点出发，沿着 word[idx]、word[idx+1]……逐字符下沉；某个字符没有分支就立即跳出循环；每走到一个带结束标记的节点，就说明 word[idx..i] 是词典里的一个单词，递归询问 dfs(i + 1, count + 1)。为什么没有分支时可以直接跳出而不是继续：字典树上不存在这条路径，意味着以 idx 开头、长度更长的任何片段都不可能是词典中的单词，继续延伸纯属浪费。为什么每遇到结束标记都要尝试递归而不是只取最长或最短的那个：切分方案可能有多种，贪心地只取某一种会漏解，例如 "catsdog" 在 "cat" 处切和在 "cats" 处切会导向完全不同的结果，必须都试。

第七步：任意一次递归返回真就把缓存写为 1 并立即返回真；所有分支都失败则把缓存写为 0 并返回假。 为什么可以提前返回：只需要存在一种合法切分即可，不必穷举全部方案。为什么失败时也要写缓存：失败的结论同样值得复用，否则同一个死路会被反复探索。

第八步：判定为真则加入结果，随后无论真假都把当前词插入字典树。 后续单词才能使用它作为组件；题目保证输入无重复项，不需要结果去重。

示例：按长度处理 ["cat","cats","dog","catsdogcats"]。判定 "catsdogcats" 时，树中已有 cat、cats、dog；DFS 可找到 cats | dog | cats，共 3 段，因此加入答案。当前词尚未插入，不存在整词匹配自身的路径。

代码实现

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

// 核心实现：字典树 + DFS 计数，维护必要状态并避免重复处理。
class Solution {
    static class Node {
        Node[] next = new Node[26];
        boolean end;
    }

    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        Arrays.sort(words, Comparator.comparingInt(String::length));
        Node root = new Node();
        List<String> res = new ArrayList<>();
        for (String w : words) {
            if (w.length() == 0) {
                continue;
            }
            int[] memo = new int[w.length() + 1];
            Arrays.fill(memo, -1);
            if (dfs(root, w, 0, 0, memo)) {
                res.add(w);
            }
            insert(root, w);
        }
        return res;
    }

    private boolean dfs(Node root, String w, int idx, int count, int[] memo) {
        if (idx == w.length()) {
            return count >= 2;
        }
        if (memo[idx] != -1) {
            return memo[idx] == 1;
        }

        Node cur = root;
        for (int i = idx; i < w.length(); i++) {
            int p = w.charAt(i) - 'a';
            if (cur.next[p] == null) {
                break;
            }
            cur = cur.next[p];
            if (cur.end) {
                if (dfs(root, w, i + 1, count + 1, memo)) {
                    memo[idx] = 1;
                    return true;
                }
            }
        }

        memo[idx] = 0;
        return false;
    }

    private void insert(Node root, String w) {
        Node cur = root;
        for (int i = 0; i < w.length(); i++) {
            int p = w.charAt(i) - 'a';
            if (cur.next[p] == null) {
                cur.next[p] = new Node();
            }
            cur = cur.next[p];
        }
        cur.end = true;
    }
}

import "sort"

// 核心实现：字典树 + DFS 计数，维护必要状态并避免重复处理。
type trieNode struct {
	next [26]*trieNode
	end  bool
}

func findAllConcatenatedWordsInADict(words []string) []string {
	sort.Slice(words, func(i, j int) bool {
		return len(words[i]) < len(words[j])
	})
	root := &trieNode{}
	res := make([]string, 0)
	for _, w := range words {
		if len(w) == 0 {
			continue
		}
		memo := make([]int, len(w)+1)
		for i := 0; i < len(memo); i++ {
			memo[i] = -1
		}
		if dfs472(root, w, 0, 0, memo) {
			res = append(res, w)
		}
		insert(root, w)
	}
	return res
}

func dfs472(root *trieNode, w string, idx int, count int, memo []int) bool {
	if idx == len(w) {
		return count >= 2
	}
	if memo[idx] != -1 {
		return memo[idx] == 1
	}

	cur := root
	for i := idx; i < len(w); i++ {
		p := int(w[i] - 'a')
		if cur.next[p] == nil {
			break
		}
		cur = cur.next[p]
		if cur.end {
			if dfs472(root, w, i+1, count+1, memo) {
				memo[idx] = 1
				return true
			}
		}
	}

	memo[idx] = 0
	return false
}

func insert(root *trieNode, w string) {
	cur := root
	for i := 0; i < len(w); i++ {
		p := int(w[i] - 'a')
		if cur.next[p] == nil {
			cur.next[p] = &trieNode{}
		}
		cur = cur.next[p]
	}
	cur.end = true
}

复杂度分析

时间复杂度：$O(W \log W + \sum L_i^2)$，其中 $W$ 是单词数、$L_i$ 是第 i 个单词的长度。排序按长度需要 $O(W \log W)$；每个单词至多展开 $L_i$ 个起点，每个起点沿字典树前进至多 $L_i$ 步。

空间复杂度：$O(\sum L_i)$。凭什么：字典树的节点总数被所有单词的字符总数界住；每个单词判定时的记忆化数组是 $O(L)$ 且用完即弃；递归深度不超过 L，栈开销同样是 $O(L)$。

关键点总结

「从某个位置出发，判断哪些前缀属于词典」这一查询模式是字典树的标准适用场景。它比哈希集合优在两点：沿字符增量推进免去子串截取，以及无匹配时能立即剪枝。凡是单词拆分类题目里词典很大或单词很长，都应该优先考虑换成字典树。

「至少拆成两段」这类计数约束要落在递归的出口条件上，而不是靠事后过滤或提前把自身从词典里删掉。把约束写进出口既简洁又不会遗漏，删除再恢复词典项的写法在有重复前缀时极易出错。

记忆化的键要「刚好」覆盖会影响结论的变量。本题只用 idx 作键的合法性依赖一个具体论证：除起点外任何被递归到的位置都已满足 count ≥ 1，此时结论不再依赖 count。这类化简一定要能说出理由，不能靠试。

遇到结束标记时必须尝试所有切法而非贪心取一种。切分问题的解空间是树形的，任何贪心裁剪都需要单独证明，通常证不出来。

空串是词典类问题的经典陷阱，它会让「消耗零个字符却推进一步」成为可能，从而制造无限递归。凡是按片段推进的算法，都要确保每一步严格消耗输入。

面试视角：面试官通常先问 139 单词拆分热身，再抛出本题，考察点是「词典与待拆单词同源时如何排除自身」以及「如何把 $O(L^2)$ 的子串查询优化掉」。回答时先给出哈希集合版的动态规划，再主动提出字典树优化并说明它省在哪里，最后解释 count 约束的处理方式。常见追问是「按长度排序后逐步建树能否进一步优化」——可以，把单词按长度升序处理并只用比当前更短的单词建树，就天然保证了拆分片段严格更短，也能省掉计数判断。

易错点总结

错误写法：先把全部单词插入字典树，且走到末尾不检查片段数。用例 words = ["cat", "dog"] → 每个词都能匹配自身一次，错误地全部入选。

错误写法：允许空串作为一个切分片段并递归到同一 idx。用例 words = ["", "a"] → 递归没有消耗字符，最终栈溢出；空串应直接跳过。

错误写法：结果里包含空串。用例 words = [""] → 空串被判定或直接收入答案，返回 [""]，正确答案是空列表。

错误写法：省掉记忆化。用例由若干个 "a" 与 "aa" 构成、待判定单词为长串全 a 的数据 → 切分路径数呈指数增长，直接超时。

错误写法：记忆化数组在所有单词之间共用一份且不清空。用例 words = ["cat", "cats", "catsdog", "dog"] → 前一个单词在下标 3 处的结论被后一个单词误用，判定结果错乱。

错误写法：把末尾判断写在查缓存之后。用例任意能被多路径到达末尾的单词，如 "aaaa" → memo[len] 被写入与某个特定 count 绑定的结论，后续路径读到错误缓存，可能把非连接词判为连接词。

错误写法：遇到结束标记时只递归一次就返回，不再继续下沉尝试更长的前缀。用例 words = ["cat", "cats", "dog", "catsdog"] → 在 "cat" 处切分后剩下 "sdog" 无解就直接放弃，漏掉在 "cats" 处切分的正确方案，"catsdog" 未被收入答案。

错误写法：字符下标计算写成 w.charAt(i) - 'A'。用例全小写输入 → 下标变成 32 以上，数组越界崩溃。

错误写法：用哈希集合存词典且每次都 word.substring(j, i) 截取判断。用例单词长度接近上限且数量达 $10^4$ → 每次截取产生 $O(L)$ 拷贝，总代价升到 $O(\sum L^3)$ 量级，超时。

错误写法：递归时 count 忘记加一，写成 dfs(i + 1, count)。用例 words = ["cat", "dog", "catdog"] → count 恒为 0，走到末尾时 0 >= 2 为假，返回空列表，正确答案是 ["catdog"]。

相似题目

题目	难度	考察点
139. 单词拆分	中等	词典与待拆串相互独立，只判可行性且不限片段数量，是本题去掉计数约束的版本
140. 单词拆分 II	困难	要输出全部拆分方案，记忆化缓存的不再是布尔值而是方案列表
208. 实现 Trie (前缀树)	中等	单独练习字典树的插入与前缀查询，是本题的前置基本功
212. 单词搜索 II	困难	字典树配合网格回溯，考察在搜索过程中用树结构同时匹配多个模式串
648. 单词替换	中等	沿字典树下沉找最短匹配前缀，与本题「找所有匹配前缀」形成对照
820. 单词的压缩编码	中等	把单词倒序插入字典树以处理后缀共享，训练对字典树方向的灵活运用