LeetCode 面试题 17.17. 多次搜索

2026-03-28 HGNULB 约 6 分钟

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

分类

题目描述

✅ 面试题 17.17. 多次搜索

题意分析

给一个长字符串 big 和多个短字符串 smalls，按 smalls 的原顺序返回每个短串在 big 中所有起始下标。短串可能彼此相同，也可能互为前缀；空串的结果为空。

对每个短串单独调用朴素查找会反复扫描 big，相同前缀也被重复比较。把所有非空短串放进同一棵 Trie 后，可以从 big 的每个起点沿 Trie 向后走：路径存在说明仍可能匹配某些短串，节点是单词终点就记录该起点。

终点不能只存一个布尔值。若 smalls 中有重复字符串，同一个 Trie 节点要对应多个原下标，答案也必须分别写入这些位置。

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

核心思路

Trie 节点保存 26 个孩子和 wordIndexes 列表。建树时，短串结束在哪个节点，就把它在 smalls 中的下标加入该列表。

对每个 start，从根开始扫描 big[start..]。当前字符没有对应孩子时，任何更长前缀都不可能匹配，立即停止；进入节点后，把 start 加入该节点所有终止短串的答案。

循环不变量是：扫描到 end 后，node 表示 big[start..end] 在 Trie 中的节点；该节点上的每个 wordIndex 都对应一个恰好从 start 开始、在 end 结束的完整短串。

例：big="mississippi"，smalls=["is","ppi","hi","sis","i","ssippi"]。从 start=1 走到字符 i 时命中短串 "i"，再走到 s 时命中 "is"；从 start=3 命中 "sis"；从 start=5 命中 "ssippi"。最终结果为 [[1,4],[8],[],[3],[1,4,7,10],[5]]。因为 start 按升序枚举，每个结果列表天然有序。

解题步骤

创建 Trie 根节点和与 smalls 等长的结果容器。

把每个非空短串插入 Trie，终点记录其原始下标；空串保持空结果。

枚举 big 的每个 start。

从 start 向右沿 Trie 匹配，路径断开就停止当前起点。

每到一个终点节点，把 start 写入其中所有 wordIndexes 对应的结果。

Java 把列表转换为二维数组；Go 可直接返回二维切片。

代码实现

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)
}

复杂度分析

设 B 为 big 长度，S 为所有短串总长度，L 为最长短串长度，Z 为所有匹配结果总数。

时间复杂度：O(S + BL + Z)。建 Trie 为 O(S)；每个起点最多走 L 步；写答案本身需要 O(Z)。

空间复杂度：O(S + Z)，Trie 节点与终点下标共 O(S)，结果占 O(Z)。

关键点总结

Trie 合并了短串的公共前缀，避免为每个模式重复做同样比较。

终点保存下标列表，才能同时处理重复短串和一个位置命中多个短串。

路径断开立即停止；最长只需看 L 个字符。

面试追问若 B 很长且模式很多，可进一步构建 Aho–Corasick 自动机，通过失败指针把查询降到 O(B+S+Z)，代价是实现复杂度显著增加。

易错点总结

终点只存一个下标：smalls=["a","a"]、big="a" 时第二个短串结果会丢失，正确结果两项都应是 [0]。

命中一个终点就停止：smalls=["a","ab"]、big="ab" 会只记录 "a"，漏掉更长的 "ab"。

记录 end 而不是 start：短串 "is" 在 "miss" 中从 1 开始、2 结束，题目要求写 1。

把空串插入根节点并在每个起点记录：题目约定空短串结果为空，会错误输出 big 的所有位置。

按哈希表遍历短串输出：会打乱 smalls 的原顺序；结果容器必须一开始就按原下标分配。

假设字符任意却仍用 26 个孩子：当前数组实现依赖小写字母约束；字符集扩展时应改为 Map。

相似题目

题目	难度	考察点
208. 实现 Trie	中等	Trie 基础操作
212. 单词搜索 II	困难	Trie 合并多个模式的网格搜索
30. 串联所有单词的子串	困难	多模式匹配与窗口计数