leetcode-每日一题745. 前缀和后缀搜索(哈希和字典树)

题目链接：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
}

复杂度分析