题目链接：https://leetcode.cn/problems/prefix-and-suffix-search/
思路
方法一、用哈希表记录每个单词的前缀和后缀组合
直接想法
如果我们用前缀 prefix 和 后缀 suff去暴力对比所有单词肯定会超时，我们可以先把单词里所有的前缀后缀组合，中间用特殊符号@连接，对应的最大下标存入哈希表中。搜索时，用特殊符号@连接前缀后缀，在哈希表中进行搜索
算法
1.把WordFilter类自定义为 map[string]int, 用于所有的前缀后缀组合的最大下标
2.Constructor函数 遍历所有单词，把单词里所有的前缀后缀组合，中间用特殊符号@连接，对应的最大下标存入哈希表WordFilter中
3.F方法用来判断前缀+ @ +后缀的组合是否存在于哈希表中
代码示例
type WordFilter map[string]int func Constructor(words []string) WordFilter { wf := WordFilter{} for i := range words{ for j, n := 1, len(words[i]); j <= n; j++{ for k := 0; k < n; k++{ wf[words[i][:j] + "@" + words[i][k:]] = i } } } return wf } func (wf WordFilter) F(pref, suff string) int { if i, ok := wf[pref + "@" + suff]; ok{ return i } return -1 }
复杂度分析
方法二、字典树
直接想法
这道题首先想到的就是构造前缀、后缀字典树。其中树节点储存包含此前（后）缀的单词索引。在后续调用F方法时，一次遍历前后缀字典树，找到满足要求的前后缀单词索引集合，然后找出两个集合中最大的相同值，即为题解。
算法
1.构造前缀、后缀字典树
2.Constructor函数 把所有单词的前缀、后缀下标存入当前前缀字典树和后缀字典树结点的idx数组
3.F方法通过找到pref在前缀字典树的结点和suff在后缀字典树的结点，找到两个结点中idx数组中相同的最大下标输出
代码示例
type trie struct { next []*trie idx []int } type WordFilter struct { pref,suff []*trie } func Constructor(words []string) WordFilter { pref, suff := make([]*trie, 26), make([]*trie, 26) for i, word := range words { pf, sf, n := pref, suff, len(word) for x, y := 0, n - 1; x < n && y >= 0; x, y = x + 1, y - 1 { //构造前缀，把所有单词前缀组合下标在当前前缀字典树结点idx数组里 a := int(word[x] - 'a') if pf[a] == nil { pf[a] = &trie{ next: make([]*trie, 26), idx: []int{i}, } } else { pf[a].idx = append(pf[a].idx, i) } pf = pf[a].next //构造后缀，把所有单词后缀组合下标在当前后缀字典树结点idx数组里 a = int(word[y] - 'a') if sf[a] == nil { sf[a] = &trie{next: make([]*trie, 26), idx: []int{i}} } else { sf[a].idx = append(sf[a].idx, i) } sf = sf[a].next } } return WordFilter{pref: pref, suff: suff} } func (this *WordFilter) F(pref string, suff string) int { p := this.pref var prefCandicates, suffCandicates []int for i := range pref { c := int(pref[i] - 'a') if p[c] == nil { return -1 } //完全匹配前缀 if i == len(pref)-1 { prefCandicates = p[c].idx } p = p[c].next } q := this.suff for i := len(suff) - 1; i >= 0; i-- { c := int(suff[i] - 'a') if q[c] == nil { return -1 } //完全匹配后缀 if i == 0 { suffCandicates = q[c].idx } q = q[c].next } i, j := len(prefCandicates)-1, len(suffCandicates)-1 for i > -1 && j > -1 { //前缀和后缀存在于一个单词 if prefCandicates[i] == suffCandicates[j] { return prefCandicates[i] } //尽量找到最大下标 if prefCandicates[i] < suffCandicates[j] { j-- } else { i-- } } return -1 }
复杂度分析
