题目描述
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 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.
Hint #1
For a word like “test”, consider “#test”, “t#test”, “st#test”, “est#test”, “test#test”. Then if we have a query like prefix = “te”, suffix = “t”, we can find it by searching for something we’ve inserted starting with “t#te”.
问题分析
首先，既然是有关字符串搜索匹配的问题，那么trie tree自然会被考虑；因此，最朴素的想法就是对字符串A，正序和逆序方式各自添加到 trie tree 中，然后查找时分别查找prefix 和 suffix，并找出符合条件的索引最大的；
经过这么多题目的“洗礼”，极大概率这种方式会TLE；所以不用考虑了。。。
想了一段时间后，没有太好的思路；查看Hint，发现题目提示可以针对每一个suffix，将之添加到原有字符串之前，对这个新拼接而成的字符串再进行搜索
这个Hint还是很直接的，核心思路都给出了；所以我们只要按照该思路写就行，代码如下
示例代码
type WordFilter struct {
trie *trie
}
func Constructor(words []string) WordFilter {
wf := WordFilter{trie: &trie{
nexts: [27]*trie{},
}}
// 将words中每一个word插入到trie tree中
for i := 0; i < len(words); i++ {
wf.insert(words[i], i)
}
return wf
}
func (this *WordFilter) F(prefix string, suffix string) int {
// 这里为了分割suffix和prefix，使用"{"进行拼接；这是从评论区看到的一个trick
// ascii中，‘z’后面一个字符就是'{'；因此我们可以通过 word[i] - 'a' 来得到连续的区间[0, 26]
// 这也是为什么初始化时，nexts长度为27的原因
word := suffix + "{" + prefix
t := this.trie
for i := 0; i < len(word); i++ {
j := word[i] - 'a'
if t.nexts[j] == nil {
return -1
}
t = t.nexts[j]
}
return t.maxidx
}
func (this *WordFilter) insert(word string, idx int) {
for i := 0; i < len(word); i++ {
newword := word[i:] + "{" + word
this.trie.insert(newword, idx)
}
}
type trie struct {
nexts [27]*trie
// 相比普通的trie tree, 少了一个isWord的标识，多了一个maxidx;
// 这里maxidx表示以到nexts为结尾的单词的最大下标
// 不需要isWord标识是否为字符串结束标识，是因为我们仅需要查找符合组合后字符串的prefix是否存在
// 如果存在，该prefix的maxidx等于该字符串的maxidx
maxidx int
}
func (t *trie) insert(word string, idx int) {
// trie tree的插入
for i := 0; i < len(word); i++ {
j := word[i] - 'a'
if t.nexts[j] == nil {
t.nexts[j] = &trie{
nexts: [27]*trie{},
}
}
t = t.nexts[word[i]-'a']
// 注意这里，每次都会将路径中的节点的maxidx更新为当前的idx
// 即如果字符串A是B的prefix，等同于A与B拥有相同的prefix；
// 那么我们插入B时，显然要讲A的maxidx也一并更新
t.maxidx = idx
}
}
/**
* Your WordFilter object will be instantiated and called as such:
* obj := Constructor(words);
* param_1 := obj.F(prefix,suffix);
*/
v1.5.2