记录生活中的点点滴滴

0%

前缀树

刷力扣才算搞明白前缀树这个数据结构,以前就知道前缀,也不太明白,现在发现这个数据结构还是很有用的,它可以利用词的公共前缀缩小查词范围、通过状态间的映射关系避免了字符的遍历,从而达到高效检索的目的!

所以现在赶紧写一篇博客记录一下自己的这一方面的盲区,嘿嘿!

前缀树

前缀树又称为单词查找树,是一种树形的结构,用于存储大量的字符串,它的优点是:利用字符串的公共前缀来节约存储空间。

Trie树主要是利用词的公共前缀缩小查词范围、通过状态间的映射关系避免了字符的遍历,从而达到高效检索的目的。

说白了,举个例子,就是如果我们在百度的搜索框里面写一个a,下面会提示一大堆a开头的:

我们不用搞的那么复杂,就按字符串:

{goog,googl,google,bai,baidu,gi}

就这些字符串,我们可以自己构造一个前缀树,因为很多前缀都想用,可以重复利用。

其实能看懂这个图就可以了,至于孩子节点,我们可以用一个map集合实现,当然也可以用一个数组实现!

208. 实现 Trie (前缀树)

好的,还是做题吧,coding起来才行,下面这道题:

让我们自己实现一个前缀树,代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Trie {

/** Initialize your data structure here. */
public Trie() {

}

/** Inserts a word into the trie. */
public void insert(String word) {

}

/** Returns if the word is in the trie. */
public boolean search(String word) {

}

/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {

}
}

/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/

现需要定义一个TrieNode节点类吧,孩子按照map还是数组,我们看看所有都只有小写,所以用数组就可以,26的size即可,还得需要一个boolean字段判断从根到当前节点是只是一个路径,还是是一个单词,当然还得需要一个String类型的去记录单词这个字段,先把这个TrieNode类写出来:

1
2
3
4
5
6
//前缀树节点
class TrieNode{
TrieNode[] child = new TrieNode[26];//孩子节点,一共26个
boolean isWord;//当前树到此是否是单词
String word;//如果是的话,单词
}

有了这个类,去定义一个根节点,当然根节点不保存数据,然后insert字符串,一个一个去遍历树,没有的话添加设置即可!判断那两个方法其实就是从根节点去遍历看看是否符合条件,也不难!

总的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Trie {
//前缀树节点
class TrieNode{
TrieNode[] child = new TrieNode[26];//孩子节点,一共26个
boolean isWord;//当前树到此是否是单词
String word;//如果是的话,单词
}
TrieNode root;//当前对象的根节点

/** Initialize your data structure here. */
public Trie() {
root = new TrieNode();//初始化根节点
}

/** Inserts a word into the trie. */
public void insert(String word) {
char[] charArray = word.toCharArray();
int len = charArray.length;
TrieNode p = root;
for(int i=0;i<len;i++){
if(p.child[charArray[i]-'a']==null){//如果没有初始化
//初始化并且将c赋值
p.child[charArray[i]-'a'] = new TrieNode();
}
p = p.child[charArray[i]-'a'];
}
p.isWord = true;
p.word = word;
}

/** Returns if the word is in the trie. */
//查询的话必须要求isWord字段为true才行
public boolean search(String word) {
TrieNode lastTrieNode = getLastTrieNode(word);
if(lastTrieNode==null){
return false;
}else{
return lastTrieNode.isWord;
}
}

//startsWith要求只要查得到即可,不要求isWord字段
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
return getLastTrieNode(prefix)!=null ? true : false;
}

//这个方法实现代码的复用,因为startsWith和search方法前面都是相同的逻辑
//只要全部匹配成,看最后一个是不是单词
//当然如果前面就有不匹配的,这个方法会直接返回null
public TrieNode getLastTrieNode(String prefix){
char[] charArray = prefix.toCharArray();
int len = charArray.length;
TrieNode p = root;
int i = 0;
for(;i<len;i++){
if(p.child[charArray[i]-'a']==null){
return null;
}
p = p.child[charArray[i]-'a'];
}
return p;
}
}

720. 词典中最长的单词

大体还复用上一次的TrieNode类,然后就是逻辑不太一样而已,它的要求是单词的所有前缀都存在,且长度最大,也就是深度最大,如果相同返回字典序最前的。

OK,主体逻辑需要用递归去完成,代码如下,就不详细写过程了,都在注释上:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
//前缀树节点
class TrieNode{
TrieNode[] child = new TrieNode[26];//孩子节点,一共26个
boolean isWord;//当前树到此是否是单词
String word;//如果是的话,单词
}
TrieNode root;//当前对象的根节点
public String longestWord(String[] words) {
root = new TrieNode();
for(String word : words){
insert(word);
}
dfs(root,0);
return res;
}
//插入字符串
public void insert(String word){
char[] charArray = word.toCharArray();
int len = charArray.length;
TrieNode p = root;
for(int i=0;i<len;i++){
if(p.child[charArray[i]-'a']==null){//如果没有初始化
//初始化并且将c赋值
p.child[charArray[i]-'a'] = new TrieNode();
}
p = p.child[charArray[i]-'a'];
}
p.isWord = true;
p.word = word;
}
//最大深度
int maxDepth = 0;
//最终的结果字符串
String res = "";
//题目要求必须得有前缀,而且要找最长的,而且如果有多个,找字典序最前面的
//这个dfs是根据题目要求写的,借助前面两个字段
public void dfs(TrieNode root,int depth){
if(depth>0 && !root.isWord){
return;
}
if(depth > maxDepth){
maxDepth = depth;
res = root.word;
}
for(TrieNode node : root.child){
if(node!=null){
dfs(node,depth+1);
}
}
}
}

OK,收工!今天只是简单地了解了一下这个数据结构,用这两道题去巩固所学的并应用,以后肯定还会遇到类似的,到时候能有感觉就行,加油!

对了,贴一下今天打卡的力扣每日一题,也是用到了前缀树,就是因为这个才学了这么多的,题以及解答如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
class TrieNode{
TrieNode[] child = new TrieNode[2];
}
private TrieNode root = new TrieNode();
private final int MAX_INT_BITS = 30;//最长31位

public void add(int num){
TrieNode p = root;
for(int i=MAX_INT_BITS;i>=0;i--){
int bit = num>>i & 1;
if(p.child[bit]==null){
p.child[bit] = new TrieNode();
}
p = p.child[bit];
}
}
public int search(int num){
TrieNode p = root;
int res = 0;
for(int i=MAX_INT_BITS;i>=0;i--){
int bit = num>>i & 1;
if(p.child[bit^1]!=null){
res+=(1<<i);
p = p.child[bit^1];
}else{
p = p.child[bit];
}
}
return res;
}
public int findMaximumXOR(int[] nums) {
int res = 0;
for(int num : nums){
add(num);
res = Math.max(res,search(num));
}
return res;
}
}