745. 前缀和后缀搜索
设计一个包含一些单词的特殊词典，并能够通过前缀和后缀来检索单词。
实现 WordFilter 类：
WordFilter(string[] words) 使用词典中的单词 words 初始化对象。f(string pref, string suff) 返回词典中具有前缀 prefix 和后缀 suff 的单词的下标。如果存在不止一个满足要求的下标，返回其中 最大的下标 。如果不存在这样的单词，返回 -1 。
示例：
输入
["WordFilter", "f"]
[[["apple"]], ["a", "e"]]
输出
[null, 0]
解释
WordFilter wordFilter = new WordFilter(["apple"]);
wordFilter.f("a", "e"); // 返回 0 ，因为下标为 0 的单词：前缀 prefix = "a" 且 后缀 suff = "e" 。
提示：
1 <= words.length <= 1041 <= words[i].length <= 71 <= pref.length, suff.length <= 7words[i]、pref 和 suff 仅由小写英文字母组成f 执行 104 次调用相似题目
原站题解
java 解法, 执行用时: 657 ms, 内存消耗: 237.6 MB, 提交时间: 2023-06-12 16:06:58
class WordFilter {
Trie trie;
String weightKey;
public WordFilter(String[] words) {
trie = new Trie();
weightKey = "##";
for (int i = 0; i < words.length; i++) {
String word = words[i];
Trie cur = trie;
int m = word.length();
for (int j = 0; j < m; j++) {
Trie tmp = cur;
for (int k = j; k < m; k++) {
String key = new StringBuilder().append(word.charAt(k)).append('#').toString();
if (!tmp.children.containsKey(key)) {
tmp.children.put(key, new Trie());
}
tmp = tmp.children.get(key);
tmp.weight.put(weightKey, i);
}
tmp = cur;
for (int k = j; k < m; k++) {
String key = new StringBuilder().append('#').append(word.charAt(m - k - 1)).toString();
if (!tmp.children.containsKey(key)) {
tmp.children.put(key, new Trie());
}
tmp = tmp.children.get(key);
tmp.weight.put(weightKey, i);
}
String key = new StringBuilder().append(word.charAt(j)).append(word.charAt(m - j - 1)).toString();
if (!cur.children.containsKey(key)) {
cur.children.put(key, new Trie());
}
cur = cur.children.get(key);
cur.weight.put(weightKey, i);
}
}
}
public int f(String pref, String suff) {
Trie cur = trie;
int m = Math.max(pref.length(), suff.length());
for (int i = 0; i < m; i++) {
char c1 = i < pref.length() ? pref.charAt(i) : '#';
char c2 = i < suff.length() ? suff.charAt(suff.length() - 1 - i) : '#';
String key = new StringBuilder().append(c1).append(c2).toString();
if (!cur.children.containsKey(key)) {
return -1;
}
cur = cur.children.get(key);
}
return cur.weight.get(weightKey);
}
}
class Trie {
Map<String, Trie> children;
Map<String, Integer> weight;
public Trie() {
children = new HashMap<String, Trie>();
weight = new HashMap<String, Integer>();
}
}
/**
* Your WordFilter object will be instantiated and called as such:
* WordFilter obj = new WordFilter(words);
* int param_1 = obj.f(pref,suff);
*/
python3 解法, 执行用时: 2388 ms, 内存消耗: 158.4 MB, 提交时间: 2023-06-12 16:06:34
# 字典树
class WordFilter:
def __init__(self, words: List[str]):
self.trie = {}
self.weightKey = ('#', '#')
for i, word in enumerate(words):
cur = self.trie
m = len(word)
for j in range(m):
tmp = cur
for k in range(j, m):
key = (word[k], '#')
if key not in tmp:
tmp[key] = {}
tmp = tmp[key]
tmp[self.weightKey] = i
tmp = cur
for k in range(j, m):
key = ('#', word[-k - 1])
if key not in tmp:
tmp[key] = {}
tmp = tmp[key]
tmp[self.weightKey] = i
key = (word[j], word[-j - 1])
if key not in cur:
cur[key] = {}
cur = cur[key]
cur[self.weightKey] = i
def f(self, pref: str, suff: str) -> int:
cur = self.trie
for key in zip_longest(pref, suff[::-1], fillvalue='#'):
if key not in cur:
return -1
cur = cur[key]
return cur[self.weightKey]
# Your WordFilter object will be instantiated and called as such:
# obj = WordFilter(words)
# param_1 = obj.f(pref,suff)
java 解法, 执行用时: 573 ms, 内存消耗: 95.2 MB, 提交时间: 2023-06-12 16:06:12
class WordFilter {
Map<String, Integer> dictionary;
public WordFilter(String[] words) {
dictionary = new HashMap<String, Integer>();
for (int i = 0; i < words.length; i++) {
String word = words[i];
int m = word.length();
for (int prefixLength = 1; prefixLength <= m; prefixLength++) {
for (int suffixLength = 1; suffixLength <= m; suffixLength++) {
dictionary.put(word.substring(0, prefixLength) + "#" + word.substring(m - suffixLength), i);
}
}
}
}
public int f(String pref, String suff) {
return dictionary.getOrDefault(pref + "#" + suff, -1);
}
}
/**
* Your WordFilter object will be instantiated and called as such:
* WordFilter obj = new WordFilter(words);
* int param_1 = obj.f(pref,suff);
*/
javascript 解法, 执行用时: 1012 ms, 内存消耗: 85.2 MB, 提交时间: 2023-06-12 16:05:55
/**
* @param {string[]} words
*/
var WordFilter = function(words) {
this.dictionary = new Map();
for (let i = 0; i < words.length; i++) {
const word = words[i];
const m = word.length;
for (let prefixLength = 1; prefixLength <= m; prefixLength++) {
for (let suffixLength = 1; suffixLength <= m; suffixLength++) {
this.dictionary.set(word.substring(0, prefixLength) + "#" + word.substring(m - suffixLength), i);
}
}
}
};
/**
* @param {string} pref
* @param {string} suff
* @return {number}
*/
WordFilter.prototype.f = function(pref, suff) {
if (this.dictionary.has(pref + "#" + suff)) {
return this.dictionary.get(pref + "#" + suff);
}
return -1;
};
/**
* Your WordFilter object will be instantiated and called as such:
* var obj = new WordFilter(words)
* var param_1 = obj.f(pref,suff)
*/
golang 解法, 执行用时: 576 ms, 内存消耗: 28.3 MB, 提交时间: 2023-06-12 16:05:25
type WordFilter map[string]int
func Constructor(words []string) WordFilter {
wf := WordFilter{}
for i, word := range words {
for j, n := 1, len(word); j <= n; j++ {
for k := 0; k < n; k++ {
wf[word[:j]+"#"+word[k:]] = i
}
}
}
return wf
}
func (wf WordFilter) F(pref, suff string) int {
if i, ok := wf[pref+"#"+suff]; ok {
return i
}
return -1
}
/**
* Your WordFilter object will be instantiated and called as such:
* obj := Constructor(words);
* param_1 := obj.F(pref,suff);
*/
python3 解法, 执行用时: 1164 ms, 内存消耗: 80.6 MB, 提交时间: 2023-06-12 16:05:10
# 暴力搜索
class WordFilter:
def __init__(self, words: List[str]):
self.d = {}
for i, word in enumerate(words):
m = len(word)
for prefixLength in range(1, m + 1):
for suffixLength in range(1, m + 1):
self.d[word[:prefixLength] + '#' + word[-suffixLength:]] = i
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)