745 Prefix and Suffix Search 前綴和后綴搜索
Description:
Design a special dictionary with some words that searchs the words in it by a prefix and a suffix.
Implement the WordFilter class:
WordFilter(string[] words) Initializes the object with the words in the dictionary.
f(string prefix, string suffix) Returns the index of the word in the dictionary, which has the prefix prefix and the suffix suffix. If there is more than one valid index, return the largest of them. If there is no such word in the dictionary, return -1.
Example:
Example 1:
Input
["WordFilter", "f"]
[[["apple"]], ["a", "e"]]
Output
[null, 0]
Explanation
WordFilter wordFilter = new WordFilter(["apple"]);
wordFilter.f("a", "e"); // return 0, because the word at index 0 has prefix = "a" and suffix = 'e".
Constraints:
1 <= words.length <= 15000
1 <= words[i].length <= 10
1 <= prefix.length, suffix.length <= 10
words[i], prefix and suffix consist of lower-case English letters only.
At most 15000 calls will be made to the function f.
題目描述:
設(shè)計一個包含一些單詞的特殊詞典哄辣，并能夠通過前綴和后綴來檢索單詞请梢。
實(shí)現(xiàn) WordFilter 類：
WordFilter(string[] words) 使用詞典中的單詞 words 初始化對象。
f(string prefix, string suffix) 返回詞典中具有前綴 prefix 和后綴suffix 的單詞的下標(biāo)力穗。如果存在不止一個滿足要求的下標(biāo)溢陪，返回其中 最大的下標(biāo) 。如果不存在這樣的單詞睛廊，返回 -1 。
示例 :
輸入：
["WordFilter", "f"]
[[["apple"]], ["a", "e"]]
輸出：
[null, 0]
解釋：
WordFilter wordFilter = new WordFilter(["apple"]);
wordFilter.f("a", "e"); // 返回 0 杉编，因?yàn)橄聵?biāo)為 0 的單詞的 prefix = "a" 且 suffix = 'e" 超全。
提示:
1 <= words.length <= 15000
1 <= words[i].length <= 10
1 <= prefix.length, suffix.length <= 10
words[i]、prefix 和 suffix 僅由小寫英文字母組成
最多對函數(shù) f 進(jìn)行 15000 次調(diào)用
思路:
前綴樹
將前綴和后綴用分隔符, 如 "#" 連在一起
即可用普通的前綴樹求解
時間復(fù)雜度為 O(mn ^ 2), 空間復(fù)雜度為 O(mn ^ 2), m 為 words 的長度, n 為 word 的長度
代碼:
C++:
class Trie
{
private:
Trie *children[27]{ nullptr };
int val = 0;
public:
void insert(string &word, int start, int cur_val)
{
Trie *p = this;
for (int i = start, s = word.size(); i < s; i++)
{
int cur = word[i] == '#' ? 26 : word[i] - 'a';
if (!p -> children[cur]) p -> children[cur] = new Trie;
p = p -> children[cur];
p -> val = max(p -> val, cur_val);
}
}
int search(string &word)
{
Trie *p = this;
for (int i = 0, s = word.size(); i < s; i++)
{
int cur = word[i] == '#' ? 26 : word[i] - 'a';
if (!p -> children[cur]) return -1;
else p = p -> children[cur];
}
return p -> val;
}
};
class WordFilter
{
private:
Trie root;
public:
WordFilter(vector<string>& words)
{
string cur;
for (int i = 0, s = words.size(); i < s; i++)
{
cur = words[i] + "#" + words[i];
for (int j = 0, t = words[i].size(); j <= t; j++) root.insert(cur, j, i);
}
}
int f(string prefix, string suffix)
{
string target = suffix + "#" + prefix;
return root.search(target);
}
};
/**
* Your WordFilter object will be instantiated and called as such:
* WordFilter* obj = new WordFilter(words);
* int param_1 = obj->f(prefix,suffix);
*/
Java:
class WordFilter {
private Map<String, Integer> map = new HashMap<>();
public WordFilter(String[] words) {
for (int i = 0; i < words.length; i++) for (int j = 1; j <= words[i].length(); j++) for (int k = 1; k <= words[i].length(); k++) map.put(words[i].substring(0, j) + "#" + words[i].substring(words[i].length() - k, words[i].length()), i);
}
public int f(String prefix, String suffix) {
return map.getOrDefault(prefix + "#" + suffix, -1);
}
}
/**
* Your WordFilter object will be instantiated and called as such:
* WordFilter obj = new WordFilter(words);
* int param_1 = obj.f(prefix,suffix);
*/
Python:
class WordFilter:
def __init__(self, words: List[str]):
self.d = {}
for i, w in enumerate(words):
for j in range(0, len(w) + 1):
p = w[:j]
for k in range(0, len(w) + 1):
q = w[k:]
self.d[(p, q)] = i
def f(self, prefix: str, suffix: str) -> int:
return self.d.get((prefix, suffix), -1)
# Your WordFilter object will be instantiated and called as such:
# obj = WordFilter(words)
# param_1 = obj.f(prefix,suffix)
