前缀和后缀搜索

题目描述：

设计一个包含一些单词的特殊词典，并能够通过前缀和后缀来检索单词。

实现 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 <= 104
1 <= words[i].length <= 7
1 <= pref.length, suff.length <= 7
words[i]、pref 和 suff 仅由小写英文字母组成
最多对函数 f 执行 104 次调用

思路:

时间复杂度：O(n^3),空间复杂度O()

用哈希做，暴力简单

代码:

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 (this WordFilter) F(pref string, suff string) int {
    if i,ok := this[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);
 */

代码效率：

执行用时：780 ms, 在所有 Go 提交中击败了20.00%的用户
内存消耗：30 MB, 在所有 Go 提交中击败了52.00%的用户