LeetCode

LeetCode-Trie

Trie是用来存储和查找大量string的带有结点和边的树型结构。对于字母string来讲，每个结点最多有26个子节点，如此构成一棵多叉树。这棵树的每一条从root的下一个结点到任意结点都是一个string。

Trie的结点可以如下定义：

1
2
3
4
5
6
7
8
9
10
class TrieNode {
public:
    TrieNode* next[26];
    bool is_word;

    TrieNode(bool b = false){
        is_word = b;
        memset(next, 0, sizeof(next));
    }
};

注意：

  1. memset(next, 0, sizeof(next))表示在next地址，从头开始将sizeof(next)个字节设置为0（0在此其实是nullptr，表示初始化不指向任何地址。）

  2. memset(next, 0, sizeof(next))等价于：

    1
    2
    3
    for(int i=0;i<26;i++){
        next[i] = nullptr;
    }

    手动将所有next指针域置为空。

  3. 所有next结点的is_word默认为false。

  4. 指针指向一个结点的首地址，所以一个结点的成员不同，首地址不同。

每个结点有26个子节点和一个bool型的成员。bool成员表示从root到当前结点的上一个结点形成的路径，这条路径表示的string是否存在于Trie中的。当为True时，这条路径表示的string存在于Trie，False则为不存在。看下图。

有了结点，可以构造Trie。开辟root空间即可，之后便可以向其中保存指定string，在其中搜索指定string。

1
2
3
4
5
/// Trie START
class Trie{
public:
	Trie(){ root = new TrieNode(); }
	~Trie(){ clear(root); }

初始化一个Trie，构造一个Trie结点作为root。

Trie的成员方法：

向Trie中添加string。只要遍历整个string，若没有当前字母，则新建一个结点；否则，自自由指针向下移动。

1
2
3
4
5
6
7
8
9
10
11
void insert(string word) {
       // tmp为自由指针，
       TrieNode* tmp = root;
       for(int i = 0; i < word.size(); i++){
           if(tmp->next[word[i] - 'a'] == nullptr)
               tmp->next[word[i] - 'a'] = new TrieNode();
           tmp = tmp->next[word[i]-'a'];
       }
	// 将单词结尾设为true，表示这条路径是一个单词
       tmp->is_word = true;
   }

注意：

  1. tmp->next[word[i] - 'a'] = new TrieNode();智力只是开辟了空间，并没有向其中写入当前的字母，这里是使用26个不同 的位置来唯一标识每一个字母。如果字母‘b’出现，那么next的第二个位置（next[word[i] - ‘a’]）将指向一个新的TrieNode结点，当然也可以使用其他TrieNode的实现方式，比如将26个字符作为key，将其子节点设为value，这种字典类型。下图是个例假设只有abc三个字符，将string bac插入Trie的过程：

    将“bac”插入Trie

  2. is_word默认是false，但一个单词写入trie结束后，手动将最后一个字母的下一个结点的is_word置为true。

在trie中搜索一个string：

1
2
3
4
5
6
7
8
9
10
bool search(string word) {
       // tmp指向单词的最后一个字母结点
       TrieNode* tmp = find_string(word);
	// 如果tmp（这个单词的最后一个字母）不是空且tmp的bool为true，
	// 表示由完整的这个单词
       if(tmp != nullptr && (tmp->is_word))
           return true;
       else
           return false;
   }

在trie中搜索一个前缀。与search方法唯一的区别是，不论tmp的is_word是否为true，即prefix是否是一个完整的单词，都就算找到。

1
2
3
4
5
6
7
bool startWith(string prifix) {
       TrieNode* tmp = find_string(prifix);
       if(tmp != nullptr)
           return true;
       else
           return false;
   }

从Trie 中删除一个已经存在的word。只需要将这个word末尾结点的is_word置位false即可。

1
2
3
4
5
6
7
8
9
void remove(string word){
	if (search(word)){
		TrieNode* tmp = root;
		for (int i=0;i<word.size();i++){
			tmp = tmp->next[word[i]-'a'];
		}
		tmp->is_word = false;
	}
}

Trie对象的头：

1
2
private:
	TrieNode* root;

找到word的最后一个字母的结点:

1
2
3
4
5
6
7
8
9
10
11
12
TrieNode* find_string(string word){
       TrieNode* tmp = root;
       for(int i = 0; i < word.size(); i++){
           if(tmp->next[word[i] - 'a'] != nullptr)
               tmp = tmp -> next[word[i] - 'a'];
           else {
               tmp = nullptr;
               break;
           }
       }
       return tmp;
   }

后序遍历 释放Trie

1
2
3
4
5
6
7
8
9
10
	void clear(TrieNode *root){
        for(int i = 0; i < 26; i++){
            if(root->next[i] != nullptr){
                clear(root->next[i]);
            }
        }
        delete root;
    }
};
/// Trie END

敲黑板：TrieNode结点的定义与链表结点定义，树结点定义相同。都会有若干自身类型的指针，且这些指针初始化为nullptr，表示指针不保存任何地址。当其中某个指针要指向一个新的结点时：tmp->next[word[i] - 'a'] = new TrieNode()，先开辟一个结点空间，后将其地址存入指针。如此，由结点构成的链就形成了。