学算法-Trie_Tree

发表于 | 分类于 | 阅读数

今天做了一道题，题目使用了字典树，我们来学一下：

概念

字典树被称为Trie树、前缀树，是一种数据结构
适用于字符串的查找、存储、统计和排序等

特点

  1. 根节点不含字符，除根结点外每个节点都只代表一个字符；
  2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；

1
该树最大可以表示的字符串集合为{i,in,inn,int,t,te,tea,a,at}

具体操作

插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct node{
    int next[26]={0};
};
int tot=1;
node trieNode[10001];
void insertNode(string str){
    int length=str.length();
    int now=0;
    for(int i=0;i<length;i++){
        int ch=str[i]-'a';
        if(!trieNode[now].next[ch]){
            trieNode[now].next[ch]=tot;
            tot++;
        }
        now=trieNode[now].next[ch];
    }
}

我们用编号tot来代表某一个字符在trieNode中的位置，然后用next数组来进行连接，对于每一个节点下面最多有a-z也就是26个字符，这就是next数组大小为啥设为26的原因
来解释一下：首先我们给两个测试用的字符串”test”和”exam”
对于”test”：
trieNode[0]代表的是root节点，所以now首先从0开始，我们假设有个指针指向这里，然后root节点下面此时为空，所以没有t这个字符，所以为这个t字符分配节点编号为1（tot），然后将其记在root节点所对应的next数组下的’t’-‘a’这个位置，然后指针移动到新生成的那个节点上（编号为1，也就是trieNode[now].next[ch]），发现此时该节点下面的next数组也都是空的（即没有e这个节点），然后为e字符分配一个编号为2(tot)的节点，并将其填充到next数组中的’e’-‘a’位置上，然后其余过程重复直至将所有字符分配

查询

1
2
3
4
5
6
7
8
9
10
bool searchNode(string str){
    int length=str.length();
    int now=0;
    for(int i=0;i<length;i++){
        int ch=str[i]-'a';
        if(!trieNode[now].next[ch])return false;
        now=trieNode[now].next[ch];
    }
    return true;
}

查询过程就是根据next数组来进行连接，依次往下查找
其中过程中某一环断开了，就没有查找到

如果只想查找插入的字符串，子串不能查询，如何限制呢？

插入改进

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct node{
    int next[27]={0};
};
int tot=1;
node trieNode[10001];
int e[10001]={0};
void insertNode(string str){
    int length=str.length();
    int now=0;
    for(int i=0;i<length;i++){
        int ch=str[i]-'a';
        if(!trieNode[now].next[ch]){
            trieNode[now].next[ch]=tot;
            tot++;
        }
        now=trieNode[now].next[ch];
    }
    e[now]=1;
}

增加一个数组e，我们看在进行e[now]=1的操作时，now是指向字符串最末端的字符，所以将其标记一下，意思就是它是字符串的末尾，如果查询操作查询的字符串的末尾所对应的e[now]!=1也就是说它不是该完整的字符串，只是一个子串，所以相应的查询操作改进如下：

查询改进

1
2
3
4
5
6
7
8
9
10
bool searchNode(string str){
    int length=str.length();
    int now=0;
    for(int i=0;i<length;i++){
        int ch=str[i]-'a';
        if(!trieNode[now].next[ch])return false;
        now=trieNode[now].next[ch];
    }
    return e[num]==1;
}

具体实例

给定一个单词列表，我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。
例如，如果这个列表是 [“time”, “me”, “bell”]，我们就可以将其表示为 S = “time#bell#” 和 indexes = [0, 2, 5]。
对于每一个索引，我们可以通过从字符串 S 中索引的位置开始读取字符串，直到 “#” 结束，来恢复我们之前的单词列表。
那么成功对给定单词列表进行编码的最小字符串长度是多少呢？
示例：

输入: words = [“time”, “me”, “bell”]
输出: 10
说明: S = “time#bell#” ， indexes = [0, 2, 5] 。

提示：

1 <= words.length <= 2000
1 <= words[i].length <= 7
每个单词都是小写字母 。

分析

这道题的意思是将给定的字母列表进行压缩，压缩至一个最简状态（一个字符串）：
这个字符串在满足“可以通过从字符串 S 中索引的位置开始读取字符串，直到 “#” 结束，来恢复我们之前的单词列表”这个条件下最短
注意：每一个单词的都是从索引号到#号结束，这就意味着”time”和”me”我们可以缩成”time#”和[0,2]
但是”time”和”im”就不能合并为”time”和[0,1]了，因为无法还原出”im”，只能还原为”ime”，所以只能合并为”time#im”和[0,5]
所以要进行合并的就是“短的那个位于长的那个的尾部”
所以我们可以先将列表里的字符串倒置，然后从长到短排序，将字符串依次插入字典树中，插入之前先判断字典树中是否存在，若存在，就不插了，不存在的话就插入，并且
结果+=(长度+1(‘#’))

代码

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 {
public:
    struct node{
        int next[27]={0};
    };
    node trieNode[100011];
    int tot=1;
    void insertNode(string str){
        int length=str.length();
        int now=0;
        for(int i=0;i<length;i++){
            int ch=str[i]-'a';
            if(!trieNode[now].next[ch]){
                trieNode[now].next[ch]=tot;
                tot++;
            }
            now=trieNode[now].next[ch];
        }
    }
    bool searchNode(string str){
        int length=str.length();
        int now=0;
        for(int i=0;i<length;i++){
            int ch=str[i]-'a';
            if(!trieNode[now].next[ch])return false;
            now=trieNode[now].next[ch];
        }
        return true;
    }
    string inverse(string str){
        string ans="";
        for(int i=str.length()-1;i>=0;i--){
            ans+=str[i];
        }
        return ans;
    }
    static bool cmp(string a,string b){
        return a.length()>b.length();
    }
    int minimumLengthEncoding(vector<string>& words) {
        int ans=0;
        sort(words.begin(),words.end(),cmp);
        for(int i=0;i<words.size();i++){
            string inv=inverse(words[i]);
            if(!searchNode(inv)){
                insertNode(inv);
                ans+=inv.length()+1;
            }
        }
        return ans;
    }
};