| comments | difficulty | edit_url | tags | |||||
|---|---|---|---|---|---|---|---|---|
true |
困难 |
|
设计一个包含一些单词的特殊词典，并能够通过前缀和后缀来检索单词。
实现 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)class WordFilter {
private Map<String, Integer> d = new HashMap<>();
public WordFilter(String[] words) {
for (int k = 0; k < words.length; ++k) {
String w = words[k];
int n = w.length();
for (int i = 0; i <= n; ++i) {
String a = w.substring(0, i);
for (int j = 0; j <= n; ++j) {
String b = w.substring(j);
d.put(a + "." + b, k);
}
}
}
}
public int f(String pref, String suff) {
return d.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);
*/class WordFilter {
public:
unordered_map<string, int> d;
WordFilter(vector<string>& words) {
for (int k = 0; k < words.size(); ++k) {
string w = words[k];
int n = w.size();
for (int i = 0; i <= n; ++i) {
string a = w.substr(0, i);
for (int j = 0; j <= n; ++j) {
string b = w.substr(j, n - j);
d[a + "." + b] = k;
}
}
}
}
int f(string pref, string suff) {
string key = pref + "." + suff;
if (d.count(key)) return d[key];
return -1;
}
};
/**
* Your WordFilter object will be instantiated and called as such:
* WordFilter* obj = new WordFilter(words);
* int param_1 = obj->f(pref,suff);
*/type WordFilter struct {
d map[string]int
}
func Constructor(words []string) WordFilter {
d := map[string]int{}
for k, w := range words {
n := len(w)
for i := 0; i <= n; i++ {
a := w[:i]
for j := 0; j <= n; j++ {
b := w[j:]
d[a+"."+b] = k
}
}
}
return WordFilter{d}
}
func (this *WordFilter) F(pref string, suff string) int {
if v, ok := this.d[pref+"."+suff]; ok {
return v
}
return -1
}
/**
* Your WordFilter object will be instantiated and called as such:
* obj := Constructor(words);
* param_1 := obj.F(pref,suff);
*/class Trie:
def __init__(self):
self.children = [None] * 26
self.indexes = []
def insert(self, word, i):
node = self
for c in word:
idx = ord(c) - ord("a")
if node.children[idx] is None:
node.children[idx] = Trie()
node = node.children[idx]
node.indexes.append(i)
def search(self, pref):
node = self
for c in pref:
idx = ord(c) - ord("a")
if node.children[idx] is None:
return []
node = node.children[idx]
return node.indexes
class WordFilter:
def __init__(self, words: List[str]):
self.p = Trie()
self.s = Trie()
for i, w in enumerate(words):
self.p.insert(w, i)
self.s.insert(w[::-1], i)
def f(self, pref: str, suff: str) -> int:
a = self.p.search(pref)
b = self.s.search(suff[::-1])
if not a or not b:
return -1
i, j = len(a) - 1, len(b) - 1
while ~i and ~j:
if a[i] == b[j]:
return a[i]
if a[i] > b[j]:
i -= 1
else:
j -= 1
return -1
# Your WordFilter object will be instantiated and called as such:
# obj = WordFilter(words)
# param_1 = obj.f(pref,suff)class Trie {
Trie[] children = new Trie[26];
List<Integer> indexes = new ArrayList<>();
void insert(String word, int i) {
Trie node = this;
for (char c : word.toCharArray()) {
c -= 'a';
if (node.children[c] == null) {
node.children[c] = new Trie();
}
node = node.children[c];
node.indexes.add(i);
}
}
List<Integer> search(String pref) {
Trie node = this;
for (char c : pref.toCharArray()) {
c -= 'a';
if (node.children[c] == null) {
return Collections.emptyList();
}
node = node.children[c];
}
return node.indexes;
}
}
class WordFilter {
private Trie p = new Trie();
private Trie s = new Trie();
public WordFilter(String[] words) {
for (int i = 0; i < words.length; ++i) {
String w = words[i];
p.insert(w, i);
s.insert(new StringBuilder(w).reverse().toString(), i);
}
}
public int f(String pref, String suff) {
suff = new StringBuilder(suff).reverse().toString();
List<Integer> a = p.search(pref);
List<Integer> b = s.search(suff);
if (a.isEmpty() || b.isEmpty()) {
return -1;
}
int i = a.size() - 1, j = b.size() - 1;
while (i >= 0 && j >= 0) {
int c = a.get(i), d = b.get(j);
if (c == d) {
return c;
}
if (c > d) {
--i;
} else {
--j;
}
}
return -1;
}
}
/**
* Your WordFilter object will be instantiated and called as such:
* WordFilter obj = new WordFilter(words);
* int param_1 = obj.f(pref,suff);
*/type Trie struct {
children [26]*Trie
indexes []int
}
func newTrie() *Trie {
return &Trie{indexes: []int{}}
}
func (this *Trie) insert(word string, i int) {
node := this
for _, c := range word {
idx := c - 'a'
if node.children[idx] == nil {
node.children[idx] = newTrie()
}
node = node.children[idx]
node.indexes = append(node.indexes, i)
}
}
func (this *Trie) search(pref string) []int {
node := this
for _, c := range pref {
idx := c - 'a'
if node.children[idx] == nil {
return []int{}
}
node = node.children[idx]
}
return node.indexes
}
type WordFilter struct {
p *Trie
s *Trie
}
func Constructor(words []string) WordFilter {
p := newTrie()
s := newTrie()
for i, w := range words {
p.insert(w, i)
s.insert(reverse(w), i)
}
return WordFilter{p, s}
}
func (this *WordFilter) F(pref string, suff string) int {
a := this.p.search(pref)
b := this.s.search(reverse(suff))
if len(a) == 0 || len(b) == 0 {
return -1
}
i, j := len(a)-1, len(b)-1
for i >= 0 && j >= 0 {
if a[i] == b[j] {
return a[i]
}
if a[i] > b[j] {
i--
} else {
j--
}
}
return -1
}
func reverse(w string) string {
ww := []byte(w)
for i, j := 0, len(w)-1; i < j; i++ {
ww[i], ww[j] = ww[j], ww[i]
j--
}
return string(ww)
}
/**
* Your WordFilter object will be instantiated and called as such:
* obj := Constructor(words);
* param_1 := obj.F(pref,suff);
*/