LeetCode 208. 前缀树

Posted on | Post modified: | In |
Words count in article: 951

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
示例:
Trie trie = new Trie();
trie.insert(“apple”);
trie.search(“apple”); // 返回 true
trie.search(“app”); // 返回 false
trie.startsWith(“app”); // 返回 true
trie.insert(“app”);
trie.search(“app”); // 返回 true
说明:
你可以假设所有的输入都是由小写字母 a-z 构成的。
保证所有输入均为非空字符串。

  前缀树是一种比较简单的数据结构，又名字典树。就像这个名字一样，它将输入的词汇按从前到后的字符进行索引，就像查单词时挨个输入的字符的情形。每个位置有26个可能（假设都为小写字母），因此它是一个26叉树。比如对abc,abd,ac,bc建立一个字典树

  可见，当数据的前缀有较多重复的时候，字典树可以节约较多内存。但是若杂乱无章的话可能反而增加内存消耗，因为字典树需要开辟空间来保存节点信息。图中可以看出字典树的两个特点

  • 根节点不含字符信息
  • 从根节点到某个节点途径的节点连接起来就是该节点的字符串组成

  再来看看一个基本的字典树节点需要包含哪些信息。首先需要26个指针来指向下一个节点，可以使用指针数组来方便管理，并且字典树中的数据是有确定范围的，就是26个字母，因此数组的下标就能表示下一节点的字母是什么。还需要一个标志位来表示某节点是否是一个字符串的结尾，这样才能在查询时确认是否是原始输入字符串或是该字符串的子串。

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
//C++ 70ms 44MB
const int MAXN = 26;  //假设字符为26个小写字母
class Trie {
public:
    bool is_end_str; // 标识当前结点是否是一个字符串的末尾
    Trie *next[MAXN]; // 下一个结点的指针数组，数组下标表示字母
    Trie() {
        is_end_str = false;
        memset(next, 0, sizeof(next));
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        Trie *curr = this; //使用curr来索引树
        for(auto ch : word){
            if(curr->next[ch-'a'] == NULL){
                Trie *new_node = new Trie();
                curr->next[ch-'a'] = new_node;
            }
            curr = curr->next[ch-'a'];
        }
        curr->is_end_str = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        Trie *curr = this;
        for(auto ch : word){
            if(curr->next[ch-'a'] == NULL)
                return false;
            curr = curr->next[ch-'a'];
        }
        return (curr->is_end_str);
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        Trie *curr = this;
        for(auto ch : prefix){
            if(curr->next[ch-'a'] == NULL)
                return false;
            curr = curr->next[ch-'a'];
        }
        return true;
    }
};

数组模拟Trie树

数组模拟的思想是使用二维数组，其中第一维表示树节点，第二维表示每个节点的子节点（字符），一个关键是用下标来建立它们之间的关系。

每个节点内保存的都是下一个节点的下标，如果节点内容为0，则表示该节点为空节点。建立的过程中，下标是单增的，保证每个节点的唯一性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const int N = 1e5+10;
int trie[N][26], cnt[N], idx; //下标是0的点既是根节点，也是空节点
char str[N];

void insert() {
    int cur = 0; 
    for (int i = 0; str[i]; ++ i) {
        int c = str[i] - 'a';
        if (!trie[cur][c]) trie[cur][c] = ++ idx;  // 之前没有该节点，新建
        cur = trie[cur][c];                        // 当前字符的的下一个节点
    }
    cnt[cur] ++ ;  // 在串的最后位置保存其计数
}

int query() {
    int cur = 0;
    for (int i = 0; str[i]; ++ i) {
        int c = str[i] - 'a';
        if (!trie[cur][c]) return 0; // 查找失败
        cur = trie[cur][c];          // 下一个节点
    }
    return cnt[cur];                 // 返回该串数量
}