LeetCode 472. 连接词

约 7 分钟
文章信息 6 个分类 6 个标签
分类
LeetCode CodeTop 困难 未解决 1-2 字节
标签
数组 字符串 动态规划 深度优先搜索 排序 字典树

题目描述

✅ 472. 连接词

image-20260929100725532

image-20260929100725884

题意分析

找出字典中能由至少两个较短单词依次拼接而成的连接词。每个片段都必须是字典里的完整单词，同一个单词可以使用多次；不能只把当前单词本身当作一个片段。

解法：字典树 + DFS 计数

核心思路

[!blue]

一个连接词只会使用比自己短的单词，因此先按长度从短到长处理。字典树保存已经处理的词，当前词先判断、后插入，避免整词匹配自身。输入单词互不相同，先插入的等长词也不可能恰好匹配当前整个单词，不会造成误判。

对当前词 w，定义 DFS 从下标 idx 开始拆分后缀，count 记录之前已经选了几段。从字典树根节点沿 w[idx..] 逐字前进，每遇到一个单词结束标记，就尝试在这里切开，递归拆分剩余后缀；只有走到字符串末尾且 count >= 2 才成功。

某个切分点失败后，还要继续沿字典树找更长的前缀，不能贪心只选最短或最长单词。只有对应字符分支不存在时，才可以停止延伸：既然当前前缀都不存在，更长的前缀也不可能是字典词。

不同切法可能到达相同 idx，用 memo[idx] 缓存后缀能否拆完。为什么不用同时缓存 count：对于尚未结束的内部位置 idx > 0，之前至少选了一段，而非空后缀至少还需要一段，所以只要后缀能拆完，就必然满足总段数至少为 2；初始位置则只会以 count = 0 进入。每个词使用独立缓存，避免混用不同字符串的后缀结果。

解题步骤

  1. 将单词按长度升序排序，创建空字典树和答案列表。
  2. 为当前非空单词创建 memo，以 -1 表示未计算，从 idx = 0、count = 0 开始 DFS。
  3. 沿字典树枚举当前后缀的单词前缀，在每个结束标记处尝试递归；成功则缓存 1 并返回。
  4. 所有切法都不成功时缓存 0；到达字符串末尾时检查总片段数是否至少为 2。
  5. 当前词可拆分则加入答案，随后将它插入字典树，供更长单词使用。

代码实现

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"

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+1)+T+\sum L_i^2)$，其中 W 为词数、T 为总字符数、L_i 为每个词的长度。排序和插入之外，每个词的每个后缀最多展开一次，每次最多沿字典树扫描整个后缀。
  • 空间复杂度：$O(T+W+L)$，其中 L 为最长词长；包含字典树、排序及结果列表、当前词的缓存和递归栈。

关键点总结

[!green]

  • 每个结束标记都是可尝试的断点，不能只贪心取最短或最长前缀。
  • 缓存属于当前单词，不能跨词复用。
  • 判定结束后再插入当前词，避免整词自匹配。

易错点总结

[!yellow]

  • 先插入全部词，又允许单段成功：每个词都能匹配自身。
  • 一个前缀失败就立即放弃：可能还有更长前缀可用。
  • 递归不前进下标：没有消耗字符，无法结束。
  • 片段数没有加一：终点无法满足至少两段的条件。

相似题目

题目 难度 关联与区别
139. 单词拆分 中等 同样按字典词切分，本题必须由至少两个更短词组成，不能把当前完整词自身直接当成功。
140. 单词拆分 II 困难 原题输出全部切分句子，本题只判断一个词是否存在有效多段组合。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/70856900
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！