【leetcode】【剑指offer Ⅱ】062. 实现前缀树

问题描述：

• 请你实现 Trie 类：
  • Trie() 初始化前缀树对象。
  • void insert(String word) 向前缀树中插入字符串 word。
  • boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即在检索之前已经插入）；否则，返回 false。
  • boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix，返回 true；否则，返回 false。

核心思路：

• 前缀树模板题。
• 三个函数实现思路如下：
  • Trie()：构造函数初始化一个大小为 26 的子节点数组，同时初始化一个单词结束标志 isEnd。
  • void insert(String word)：根据 word 的每一个字符进行向下移动，如果没法移动则新建 Trie 节点，移动到最后把当前的节点标志 isEnd 置为 true。【置为 true 表示当前节点为字符串结尾，即尾后】
  • boolean search(String word)：操作和上一个函数的实现差不多，不断向下移动，如果中途无法想下移动，则返回 false；如果移动到最后一个字符，还要判断当前节点标志 isEnd 是否为 true。
  • boolean startsWith(String prefix)：和前一个函数实现一样，只是最后不需要判断节点标志。

代码实现：

class Trie
{
private:
    vector<Trie*> next;
    bool isEnd;
public:
    /** Initialize your data structure here. */
    Trie(): next(26), isEnd(false) {}
    
    /** Inserts a word into the trie. */
    void insert(string word)
    {
        Trie* cur = this;
        for(char& c : word)
        {
            if(!cur->next[c - 'a']) cur->next[c - 'a'] = new Trie();
            cur = cur->next[c - 'a'];
        }
        cur->isEnd = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word)
    {
        Trie* cur = this;
        for(char& c : word)
        {
            if(!cur->next[c - 'a']) return false;
            cur = cur->next[c - 'a'];
        }
        return cur->isEnd;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix)
    {
        Trie* cur = this;
        for(char& c : prefix)
        {
            if(!cur->next[c-'a']) return false;
            cur = cur->next[c - 'a'];
        }
        return true;
    }
};
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