LeetCode 题解工作台
前缀和后缀搜索
设计一个包含一些单词的特殊词典，并能够通过前缀和后缀来检索单词。 实现 WordFilter 类： WordFilter(string[] words) 使用词典中的单词 words 初始化对象。 f(string pref, string suff) 返回词典中具有前缀 pref 和后缀 suff…
5
题型
4
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
遍历 的每个单词 ，将 的所有前缀、后缀对存放到哈希表中。 class WordFilter:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
设计一个包含一些单词的特殊词典，并能够通过前缀和后缀来检索单词。
实现 WordFilter 类：
WordFilter(string[] words)使用词典中的单词words初始化对象。f(string pref, string suff)返回词典中具有前缀pref和后缀suff的单词的下标。如果存在不止一个满足要求的下标，返回其中 最大的下标 。如果不存在这样的单词，返回-1。
示例：
输入
["WordFilter", "f"]
[[["apple"]], ["a", "e"]]
输出
[null, 0]
解释
WordFilter wordFilter = new WordFilter(["apple"]);
wordFilter.f("a", "e"); // 返回 0 ，因为下标为 0 的单词：前缀 prefix = "a" 且 后缀 suffix = "e" 。
提示：
1 <= words.length <= 1041 <= words[i].length <= 71 <= pref.length, suff.length <= 7words[i]、pref和suff仅由小写英文字母组成- 最多对函数
f执行104次调用
解题思路
方法一：暴力哈希
遍历 的每个单词 ，将 的所有前缀、后缀对存放到哈希表中。
class WordFilter:
def __init__(self, words: List[str]):
self.d = {}
for k, w in enumerate(words):
n = len(w)
for i in range(n + 1):
a = w[:i]
for j in range(n + 1):
b = w[j:]
self.d[(a, b)] = k
def f(self, pref: str, suff: str) -> int:
return self.d.get((pref, suff), -1)
# Your WordFilter object will be instantiated and called as such:
# obj = WordFilter(words)
# param_1 = obj.f(pref,suff)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(NK^2 + QK) |
| 空间 | O(NK^2) |
面试官常问的追问
外企场景- question_mark
The candidate demonstrates understanding of Trie structures and hashing for prefix-suffix matching.
- question_mark
They should consider how to optimize space usage while maintaining efficiency in multiple queries.
- question_mark
Look for attention to detail when managing combinations of prefixes and suffixes in the Trie.
常见陷阱
外企场景- error
Overcomplicating the design by not leveraging the Trie structure effectively.
- error
Failing to optimize for multiple queries by not using hash-based lookups.
- error
Not handling the space complexity efficiently, leading to excessive memory usage.
进阶变体
外企场景- arrow_right_alt
Consider modifying the problem to handle a fixed-size dictionary and optimize for multiple queries using pre-processing techniques.
- arrow_right_alt
A variant could involve supporting more complex patterns beyond simple prefix and suffix matching, like substrings.
- arrow_right_alt
Handling words with overlapping prefixes and suffixes might require additional data structures or optimizations.