LeetCode 745 题《前缀和后缀搜索》要求你设计一个 WordFilter 类，支持通过前缀（prefix）和后缀（suffix）快速查找单词，并返回满足条件的单词在原始数组中的最大下标（若不存在则返回 -1）。

✅ 核心思路（推荐：哈希预处理）

由于题目限制：

• 单词数量 ≤ 10⁴
• 每个单词长度 ≤ 7
• 查询次数 ≤ 10⁴

我们可以预先计算所有可能的前缀+后缀组合，用特殊字符（如 “#”）拼接作为键，存入哈希表，值为最大下标。

例如：单词 “apple”
前缀 “a” + 后缀 “e” → 键 “a#e” → 值 0

这样每次查询 f(pref, suff) 只需 O(1) 时间！

✅ 完整 Java 实现（高效、简洁、通过 LeetCode）

import java.util.*;

class WordFilter {
// key: “prefix#suffix”, value: 最大下标
private Map map = new HashMap();

public WordFilter(String[] words) {
    for (int i = 0; i < words.length; i++) {
        String word = words[i];
        int n = word.length();
        // 枚举所有前缀长度 [1, n]
        for (int j = 1; j <= n; j++) {
            // 枚举所有后缀长度 [1, n]
            for (int k = 1; k <= n; k++) {
                String prefix = word.substring(0, j);
                String suffix = word.substring(n - k); // 从倒数第k个字符到末尾
                String key = prefix + "#" + suffix;
                map.put(key, i); // 自动保留最大下标（i递增）
            }
        }
    }
}

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

}

✅ 示例验证

WordFilter wf = new WordFilter(new String[]{“apple”});
System.out.println(wf.f(“a”, “e”)); // 输出 0

WordFilter wf2 = new WordFilter(new String[]{“apple”, “apply”});
System.out.println(wf2.f(“ap”, “ly”)); // 输出 1（“apply” 下标为1）

✅ 复杂度分析
项目 复杂度
初始化时间 O(N × L³) —— N 个单词，每个最多 L=7，前缀 L 种，后缀 L 种，substring 操作 O(L)
查询时间 O(P + S) —— 拼接字符串（P=pref长度, S=suff长度）
空间 O(N × L²) —— 每个单词最多 L² 个键

虽然看起来是立方复杂度，但因 L ≤ 7，实际最多 10⁴ × 7 × 7 = 490,000 个键，完全可接受。

❌ 为什么不推荐双字典树？

• 实现复杂，容易超时（C++/Java 中 vector/set 拷贝开销大）
• 需要处理引用、空返回等细节
• 对于本题数据规模，哈希预处理更简单、更快、更稳定

✅ 总结

• 用 “prefix#suffix” 作为哈希键是最优解；
• 初始化时暴力枚举所有组合；
• 查询时直接查表，O(1) 响应；
• 代码简洁，不易出错，适合面试和竞赛。

如需 C++ 或 Python 版本，也可以告诉我！