题解 | #字典树的实现#
字典树的实现
http://www.nowcoder.com/practice/a55a584bc0ca4a83a272680174be113b
字典树的实现
问题描述：字典树又称为前缀树或者Trie树，是处理字符串常用的数据结构。假设组成所有单词的字符仅是‘a’～‘z’，请实现字典树的结构，并包含以下四个主要的功能。void insert(String word)：添加word，可重复添加；void delete(String word)：删除word，如果word添加过多次，仅删除一次；boolean search(String word)：查询word是否在字典树中出现过(完整的出现过，前缀式不算)；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为前缀的单词数量，其它情况不输出。
示例
输入：[["1","qwer"],["1","qwe"],["3","qwer"],["4","q"],["2","qwer"],["3","qwer"],["4","q"]]
返回值：["YES","2","NO","1"]
说明：["1","qwer"]插入字符串qwer,["1","qwe"]继续插入字符串qwe，总的字符串为qwerqwe，["3","qwer"]查询qwer是否在字符串中，返回YES，["4","q"]输出字符串中以q为前缀的单词数量(qwer，qwe)，返回2，["2","qwer"删除qwer，总的字符串为qwe，["3","qwer"]查询qwer，不在字符串中返回NO，["4","q"]查询字符串中以q为前缀的单词数量返回1。
方法一
思路分析
首先介绍字典树的基本性质如下：
- 根节点没有字符路径，除根节点外每个节点都能被一个字符路径找到
- 从根节点开始到任何一个节点，将沿途经过的节点连接起来一定为之前加入过的字符串的前缀
- 每个节点向下的所有字符串路径上的字符都不同
在具体实现过程中与字典树节点的类型有关，TrieNode类中，path表示有多少个单词共用这个节点，如此我们才能知道某字符串pre为前缀的单词数量。end表示有多少个单词以这个节点结尾，只要end大于0，那么说明存在单词以该节点结尾，亦表示该节点为终止节点。
- 在字典树上添加一个字符串：由于每一个节点下面有26个节点，因此在插入过程中，首先从根节点出发，将每一个字符串中的字符减去‘a’，得到其存储的位置下标，如果该节点为空，则新建一个节点，并将其path+1，如果该位置节点不为空，那么path+1，继续插入下一个字符，直到所有的字符遍历完成。且其最后一个字符的节点的end+1；
- 删除一个添加过的字符串：在查找的过程中如果发现某个节点为空，则表示该字符串未被插入过，否则，没查找到一个字符其path值减1，当到达最后一个字符，终止节点的end值减1
- 搜索一个字符串：与插入过程类似，不过在处理最后一个字符时，如果其对应的节点end值为0，则该节点不是终止节点，该字符串未插入过字典树中，这也是解决搜索的字符串必须完整的出现过，前缀式不算的方法。
- 返回以字符串pre作为前缀的单词数量：和查找操作同理，不断的在树中查找前缀pre，若该前缀存在，那么返回其最后一个节点的path值，如不存在直接返回0
图解
例如在插入的过程中val值加1,如果是终止节点end值加1
查找过程如下：
返回以字符串pre作为前缀的单词数量的图解过程：
JAVA核心代码
import java.util.*;
public class Solution {
/**
*
* @param operators string字符串二维数组 the ops
* @return string字符串一维数组
*/
public String[] trieU (String[][] operators) {
// write code here
int n=0;
for(String[] oper:operators)
{
if(oper[0].equals("3")||oper[0].equals("4"))
n++;
}
String[] temp=new String[n];
Trie trie=new Trie();
int id=0;
for(String[] oper:operators)
{
if(oper[0].equals("1"))
{
trie.insert(oper[1]);
}
else if(oper[0].equals("2"))
{
trie.delete(oper[1]);
}
else if(oper[0].equals("3"))
{
temp[id++]=trie.search(oper[1])?"YES":"NO";
}
else if(oper[0].equals("4"))
{
temp[id++]=String.valueOf(trie.prefixNumber(oper[1]));
}
}
return temp;
}
class Trie{
public class TrieNode {
public int path;//该节点为前缀的字符串的数量
public int end;//以该节点为终止节点的字符串数
public TrieNode[] map;
public TrieNode() {
path = 0;
end = 0;
map = new TrieNode[26];// 26个字母
}
}
TrieNode root=new TrieNode();
public void insert(String word) //向字典树中插入字符串
{
if (word == null)
return;
TrieNode node = root;
node.path++;
char[] words = word.toCharArray();
int index = 0;
for (int i = 0; i < words.length; i++) {
index = words[i] - 'a';
if (node.map[index] == null) //该位置的节点为空，创建节点
{
node.map[index] = new TrieNode();
}
node = node.map[index];
node.path++;
}
node.end++;
}
public boolean search(String word) //搜索添加过的字符串
{
if (word == null)
return false;
TrieNode node = root;
char[] words = word.toCharArray();
int index = 0;
for (int i = 0; i < words.length; i++) {
index = words[i] - 'a';//根节点后寻找的下标位置
if (node.map[index] == null)
return false;
node = node.map[index];
}
return node.end > 0;
}
public void delete(String word) {
if (search(word)) {
char[] words = word.toCharArray();
TrieNode node = root;
node.path--;
int index = 0;
for (int i = 0; i < words.length; i++) {
index = words[i] - 'a';
if (--node.map[index].path == 0) {
node.map[index] = null;
return;
}
node = node.map[index];
}
node.end--;
}
}
public int prefixNumber(String pre) {
if (pre == null)
return 0;
TrieNode node = root;
char[] pres = pre.toCharArray();
int index = 0;
for (int i = 0; i < pres.length; i++) {
index = pres[i] - 'a';
if (node.map[index] == null)//如果该位置不存在节点，则表示未插入过这样的字符串
return 0;
node = node.map[index];
}
return node.path;
}
}
} 复杂度分析
- 时间复杂度：取决于给定的操作个数以及操作下的字符串的长度，假定最大字符串长度为N，那么时间复杂度为$O(N)$
- 空间复杂度: 在构建字典树时需要用到空间，如果需要插入的所有字符串长度为N，那么需要用到的空间最大为$O(26*N)$
方法二
思路分析
在字典树上添加一个字符串过程：
- 从字典树的根结点出发
- 取出待插入字符串的第一个字符，在字典树上对应的字符路径下插入
- 根据字符串的第二个字符对应插入字典树上第二层字符路径
- 一直向下直到待插入字符串的最后一个字符，并在字典树中将其标记为终止节点
删除一个添加过的字符串与添加过程类似。
在字典树上搜索添加过的字符串的过程：（完整的出现过，前缀式不算）
- 从字典树的根结点出发
- 取出待查找字符串的第一个字符，在字典树上对应的字符路径往下搜索，
- 根据字符串的第二个字符对应寻找字典树上第二层字符路径
- 一直向下搜索直到找到字典树上的最后一个节点为终止节点，则表示该字符串是完整的出现在字典树中的，因为前缀式不算，因此最后的节点必须为终止节点。例如：向字典树中插入qwer,那么寻找qwe时，最后一个节点e不为终止节点，那么说明qwe不是添加过的字符串。
返回以字符串pre作为前缀的单词数量的过程：
- 同搜索过程一样，一直向下搜索找到最后一个节点，此时计数加一，继续向后直到找到该路径下的所有其他终止节点，则找到了所有字符串pre作为前缀的单词数量
python核心代码
#
#
# @param operators string字符串二维数组 the ops
# @return string字符串一维数组
#
class Trie(object):
def __init__(self):
self.trie = {}#设置字典数组存储end值
self.count = 0
def __repr__(self):
return str(self.trie)
def buildTree(self, wordList):
for word in wordList:
t = self.trie # 指向各节点的指针，初始化为root节点
for w in word:
if w not in t:
t[w] = {'count': 0}
t[w]['count'] += 1
t = t[w]
self.count += 1
t['end'] = 1
def add(self, word):
t = self.trie
for w in word:
if w not in t:
t[w] = {'count': 0}
t[w]['count'] += 1
t = t[w]
self.count += 1
t['end'] = 1
def delete(self, word):
# 仅仅改变end和count属性，字符串仍存在于存储中
# 先确定是否存在，若存在沿着的每条路径的count都需要-1
if not self.search(word):
return False
t = self.trie
for w in word:
t = t[w]
t['count'] -= 1
self.count -= 1
t['end'] = 0
def search(self, word):
t = self.trie
for w in word:
if w not in t:
return False
t = t[w]
if t.get('end') == 1:
return True
return False
def prefix_count(self, prefix):
t = self.trie
for w in prefix:
if w not in t:
return 0
t = t[w]
return t['count']
class Solution:
def trieU(self , operators ):
# write code here
trie = Trie()
list1=[]
n=len(operators);
for i in range(n):
if operators[i][0]=="1":
trie.add(operators[i][1])
elif operators[i][0]=="2":
trie.delete(operators[i][1])
elif operators[i][0]=="3":
test=(trie.search(operators[i][1]))
if test:
list1.append('YES')
else: list1.append('NO')
elif operators[i][0]=="4":
list1.append(trie.prefix_count(operators[i][1]))
return list1 复杂度分析
- 时间复杂度：取决于给定的操作个数以及操作下的字符串的长度，假定最大字符串长度为N，那么时间复杂度为$O(N)$
- 空间复杂度：在构建字典树时需要用到空间，如果需要插入的所有字符串长度为N，那么需要用到的空间最大为$O(26*N)$
华为工作强度 811人发布
