字典树的实现_

字典树又称为前缀树或者Trie树，是处理字符串常用的数据结构。

假设组成所有单词的字符仅是‘a’～‘z’，请实现字典树的结构，并包含以下四个主要的功能。

1. void insert(String word)：添加word，可重复添加；
2. void delete(String word)：删除word，如果word添加过多次，仅删除一次；
3. boolean search(String word)：查询word是否在字典树中出现过(完整的出现过，前缀式不算)；
4. int prefixNumber(String pre)：返回以字符串pre作为前缀的单词数量。

现在给定一个m，表示有m次操作，每次操作都为以上四种操作之一。每次操作会给定一个整数op和一个字符串word，op代表一个操作码，如果op为1，则代表添加word，op为2则代表删除word，op为3则代表查询word是否在字典树中，op为4代表返回以word为前缀的单词数量（数据保证不会删除不存在的word）。

对于每次操作，如果op为3时，如果word在字典树中，请输出“YES”，否则输出“NO”；如果op为4时，请输出返回以word为前缀的单词数量，其它情况不输出。

数据范围：操作数满足 $0\le m \le 10^5$ ，字符串长度都满足 $0 \le n \le 20$

进阶：所有操作的时间复杂度都满足 $O(n)$

package main import "strconv" /** * * @param operators string字符串二维数组 the ops * @return string字符串一维数组 */ type Tree struct{ node [26]*Tree pass int tot int } func (t *Tree) insert(word string){ tr:=t for _,ch:=range []byte(word){ if tr.node[int(ch-'a')]==nil{ tr.node[int(ch-'a')]=&Tree{} } tr=tr.node[int(ch-'a')] tr.pass++ } tr.tot++ } func (t *Tree) delete(word string){ tr:=t for _,ch:=range []byte(word){ tr=tr.node[int(ch-'a')] tr.pass-- } tr.tot-- } func (t *Tree) search(word string)bool{ tr:=t for _,ch:=range []byte(word){ if tr.node[int(ch-'a')]==nil{ return false } tr=tr.node[int(ch-'a')] } return tr.tot>0 } func (t *Tree) prefixNumber(pre string)int{ tr:=t for i,ch:=range []byte(pre){ if tr.node[int(ch-'a')]==nil{ return 0 } tr=tr.node[int(ch-'a')] if i==len(pre)-1{ break } } return tr.pass } func trieU( operators [][]string ) []string { ans:=[]string{} t:=&Tree{} for _,child:=range operators{ x,s:=child[0],child[1] if x=="1"{ t.insert(s) }else if x=="2"{ t.delete(s) }else if x=="3"{ res:=t.search(s) if res{ ans=append(ans,"YES") }else{ ans=append(ans,"NO") } }else if x=="4"{ res:=t.prefixNumber(s) ans=append(ans,strconv.Itoa(res)) } } return ans }

字典树的实现

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题