LeetCode 745. 前缀和后缀搜索

约 4 分钟
文章信息 8 个分类 5 个标签
分类
LeetCode CodeTop 困难 未解决 2-5 字节 微软 拼多多
标签
数组 字符串 哈希表 设计 字典树

题目描述

✅ 745. 前缀和后缀搜索

image-20260928224625998

image-20260928224626002

题意分析

构造词典后，会多次查询同时具有指定前缀和指定后缀的单词；多个单词符合时返回最大下标，没有符合的返回 -1。两个条件必须由同一个单词满足。题目中每个单词最多长 7，适合把匹配结果提前算好。

解法：预计算所有前后缀组合到哈希表

核心思路

[!blue]

一个长度为 n 的单词，其前缀由长度 p 唯一确定，后缀由长度 s 唯一确定。枚举 p、s 的所有取值，就能列出这个单词能够回答的所有查询，不需要在每次查询时重新扫描整个词典。

用 prefix + "#" + suffix 作为哈希表键，值保存最大匹配下标。单词只含小写字母，# 不会与原字符混淆，因此组合键能唯一恢复前后缀的分界。查询用相同方式构造键，命中的一定是同时满足这两个条件的单词；所有匹配单词都枚举过该组合，也不会漏掉候选。

按下标从小到大处理单词，相同键后写入的下标一定更大，直接覆盖即可。处理完词典后，每个键自然保留最大匹配下标，即使词典中有重复单词也成立。

前缀与后缀是对同一个字符串的两项独立约束，可以重叠，也可以都等于整个单词；枚举时不能限制 p+s <= n。

解题步骤

  • 按下标 i 递增遍历单词，取得长度 n。
  • 枚举前缀长度 p 和后缀长度 s，分别截取 word[0..p) 与 word[n-s..n)，构造组合键并写入 i。实现枚举 0..n，同时覆盖空串与整词边界。
  • 查询时构造 pref + "#" + suff，若存在就返回记录的下标，否则返回 -1。

查询结果可能是下标 0，Go 必须用映射查询的 ok 判断键是否存在，不能把零值当作未命中。

代码实现

class WordFilter {
    // 单词长度较小，构造期可以枚举所有前缀和后缀组合，把查询直接变成 O(1) 字典命中。
    private final Map<String, Integer> weight = new HashMap<>();

    public WordFilter(String[] words) {
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            int n = word.length();

            for (int p = 0; p <= n; p++) {
                String prefix = word.substring(0, p);

                for (int s = 0; s <= n; s++) {
                    String suffix = word.substring(n - s);

                    // 分隔符区分前后缀边界，递增下标覆盖后留下最大匹配
                    weight.put(prefix + "#" + suffix, i);
                }
            }
        }
    }

    public int f(String pref, String suff) {
        return weight.getOrDefault(pref + "#" + suff, -1);
    }
}

type WordFilter struct {
    // 单词长度较小，构造期可以枚举所有前缀和后缀组合，把查询直接变成 O(1) 字典命中。
    weight map[string]int
}

func Constructor(words []string) WordFilter {
    weight := make(map[string]int)
    for i, word := range words {
        n := len(word)
        for p := 0; p <= n; p++ {
            prefix := word[:p]
            for s := 0; s <= n; s++ {
                suffix := word[n-s:]
                // 分隔符区分前后缀边界，递增下标覆盖后留下最大匹配
                weight[prefix+"#"+suffix] = i
            }
        }
    }
    return WordFilter{weight: weight}
}

func (this *WordFilter) F(pref string, suff string) int {
    if idx, ok := this.weight[pref+"#"+suff]; ok {
        return idx
    }
    return -1
}

复杂度分析

  • 时间复杂度：设单词数为 $N$、最长词长为 $L$。每个单词有 $O((L+1)^2)$ 个组合，拼接与哈希键需要 $O(L+1)$ 时间，构造期望为 $O(N(L+1)^3)$。查询前缀、后缀长度分别为 $P$、$S$，构造并查找键的期望时间为 $O(P+S+1)$。
  • 空间复杂度：组合键占用的字符总量最坏为 $O(N(L+1)^3)$，每次查询另用 $O(P+S+1)$ 的临时键空间。

关键点总结

[!green]

  • 组合键需要保存前后缀的分界，避免不同组合拼成同串。
  • 覆盖写入实现最大下标，不需要保存全部历史候选。

易错点总结

[!yellow]

  • 倒序写入却仍覆盖，会留下最小匹配下标。
  • 禁止前后缀重叠，会拒绝单词 a 的前缀 a、后缀 a。
  • 漏掉整词前缀或后缀，会缺少合法查询。

相似题目

题目 难度 关联与区别
208. 实现 Trie (前缀树) 中等 前缀Trie只能解决一侧约束，本题还需结合后缀并取满足两者的最大下标。
1032. 字符流 困难 原题在字符流中只检查当前后缀，本题同时给定前缀和后缀，需合并两个条件的候选索引。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/16942092
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！