LeetCode 面试题 17.17. 多次搜索

约 6 分钟
文章信息 3 个分类 6 个标签
分类
LeetCode 中等 程序员面试金典（第 6 版）
标签
数组 字符串 哈希表 滑动窗口 字典树 字符串匹配

题目描述

✅ 面试题 17.17. 多次搜索

image-20260929010559942

题意分析

对每个短串，找出它在长串 big 中出现的全部起始下标，结果仍按 smalls 的原顺序排列，允许不同出现位置互相重叠。题目保证短串互不重复，所有字符均为小写字母；实现为空短串保留空结果。

解法：短串 Trie + 枚举长串起点

核心思路

[!blue]

多个短串可能共享前缀，逐个独立搜索会重复比较这些前缀。将所有非空短串正序插入同一棵 Trie，就能从长串的一个起点出发，同时判断哪些短串还可能匹配。

Trie 节点的孩子表示下一字符，终点记录该短串在 smalls 中的原下标，代码用 wordIndexes 列表保存。题目保证模式互不重复，所以每个终点实际对应一个原下标；这个下标用于把匹配结果写回正确的结果槽位，而不是按建树遍历顺序输出。

枚举长串中的起点 start，每次从根开始向右扫描。走到 end 时，Trie 节点恰好表示区间 big[start..end]。如果当前节点是某个词的终点，这个区间就与那个完整短串相等，应记录 start；若还有孩子，则继续向右，因为一个已匹配短串还可能是更长短串的前缀。

当前字符没有对应孩子时，就可以结束这个起点的搜索。所有更长匹配都必须先经过当前区间，它已经不对应任何模式前缀，继续增加字符也无法重新匹配。这个剪枝只结束当前 start，随后仍要从下一个起点重新尝试，所以重叠出现不会被跳过。

每一次真实出现都有唯一的起点和终点，枚举到它的起点时必能沿 Trie 到达对应终点；反过来，只有完整匹配的终点才会记录位置。因此结果不漏也不多。起点按升序处理，单个短串的结果列表自然有序，不需要再排序。

解题步骤

  1. 为每个短串预留一个结果槽位，将非空短串插入 Trie，终点记录原下标。
  2. 按升序枚举 big 的每个起点，从 Trie 根开始向右匹配。
  3. 路径断开则结束当前起点；到达词终点则把起点加入对应结果，并继续检查更长短串。
  4. 所有起点完成后，按原下标返回结果；未出现的短串仍保留空结果。

代码实现

class Solution {
    public int[][] multiSearch(String big, String[] smalls) {
        TrieNode root = new TrieNode();
        List<Integer>[] positions = new ArrayList[smalls.length];

        for (int index = 0; index < smalls.length; index++) {
            positions[index] = new ArrayList<>();

            if (!smalls[index].isEmpty()) {
                insert(root, smalls[index], index);
            }
        }

        for (int start = 0; start < big.length(); start++) {
            TrieNode node = root;

            for (int end = start; end < big.length(); end++) {
                int childIndex = big.charAt(end) - 'a';

                if (childIndex < 0 || childIndex >= 26 || node.children[childIndex] == null) {
                    break;
                }

                node = node.children[childIndex];

                for (int wordIndex : node.wordIndexes) {
                    positions[wordIndex].add(start);
                }
            }
        }

        int[][] answer = new int[smalls.length][];

        for (int index = 0; index < smalls.length; index++) {
            answer[index] = new int[positions[index].size()];

            for (int pos = 0; pos < positions[index].size(); pos++) {
                answer[index][pos] = positions[index].get(pos);
            }
        }

        return answer;
    }

    private void insert(TrieNode root, String word, int wordIndex) {
        TrieNode node = root;

        for (int pos = 0; pos < word.length(); pos++) {
            int childIndex = word.charAt(pos) - 'a';

            if (node.children[childIndex] == null) {
                node.children[childIndex] = new TrieNode();
            }

            node = node.children[childIndex];
        }

        node.wordIndexes.add(wordIndex);
    }

    private static class TrieNode {
        private TrieNode[] children = new TrieNode[26];
        private List<Integer> wordIndexes = new ArrayList<>();
    }
}

type TrieNode struct {
    children    [26]*TrieNode
    wordIndexes []int
}

func multiSearch(big string, smalls []string) [][]int {
    root := &TrieNode{}
    positions := make([][]int, len(smalls))

    for index, word := range smalls {
        if len(word) > 0 {
            insertWord(root, word, index)
        }
    }

    for start := 0; start < len(big); start++ {
        node := root
        for end := start; end < len(big); end++ {
            childIndex := int(big[end] - 'a')
            if childIndex < 0 || childIndex >= 26 || node.children[childIndex] == nil {
                break
            }

            node = node.children[childIndex]
            for _, wordIndex := range node.wordIndexes {
                positions[wordIndex] = append(positions[wordIndex], start)
            }
        }
    }

    return positions
}

func insertWord(root *TrieNode, word string, wordIndex int) {
    node := root
    for pos := 0; pos < len(word); pos++ {
        childIndex := int(word[pos] - 'a')
        if node.children[childIndex] == nil {
            node.children[childIndex] = &TrieNode{}
        }
        node = node.children[childIndex]
    }
    node.wordIndexes = append(node.wordIndexes, wordIndex)
}

复杂度分析

  • 时间复杂度：$O(Q+S+B(\min(B,L)+1)+Z)$。Q 是短串数，S 是短串总字符数，B 是长串长度，L 是最长短串长度，Z 是输出下标总数。每个起点最多匹配最长模式长度，再做一次失败检查；记录与 Java 结果转换还需处理全部输出。
  • 空间复杂度：$O(Q+S+Z+1)$，用于结果槽位、Trie、根节点和全部匹配位置。

关键点总结

[!green]

  • Trie 共享短串前缀，终点原下标保证返回顺序对应 smalls。
  • 命中短词后继续走，路径断开才结束当前起点。
  • 枚举所有起点而非跳过已匹配区间，才能保留重叠出现。

易错点总结

[!yellow]

  • 仅到达没有词终点标记的节点不能记录答案，路径存在不代表已经匹配完整词。
  • 命中一个词就停止，会漏掉以它为前缀的更长词。
  • 结果要记录 start，不是最后匹配到的 end。
  • 空短串被跳过，不应通过根节点在每个位置重复登记。
  • 不要按 Trie 或哈希表的遍历次序重排结果，结果槽位始终使用短串的原下标。

相似题目

题目 难度 关联与区别
208. 实现 Trie (前缀树) 中等 复用Trie的共享前缀，本题终点保存模式原下标并从长串所有起点扫描。
212. 单词搜索 II 困难 同样用Trie同时匹配多个词，本题是一维长串连续向右，原题在网格上回溯。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/50735352
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！