208. Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.

Example:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");   
trie.search("app");     // returns true

Note:

• You may assume that all inputs are consist of lowercase letters a-z.
• All inputs are guaranteed to be non-empty strings.

---

本题要求实现只包含26个小写字母的trie树。因为之前做过hihoCoder 1014-Trie树，所以实现起来并不费劲。 定义一个Node结构体，包含三个成员，char c表示该Node的字符，bool isWord表示以该Node结尾是否能构成一个单词，children表示该Node的26个孩子。 初始化的时候就初始化一个根节点。 插入一个单词时，不断从根节点往下创建节点，到最后一个字符所在节点时，标记isWord为true。 搜索一个单词时，也是不断从根节点往下搜索，如果到单词尾所在的Node的isWord为true，说明找到该单词，否则要么到不了最后一个字符，要么到了最后一个字符，isWord为false，都表示搜索失败。 搜索是否有某个前缀的单词存在，和搜索一个单词几乎一样，只不过最后返回时，不需要判断isWord是否为true，只要能到达prefix的最后一个字符的Node，说明后面肯定有以该字符串为前缀的单词存在。 完整代码如下：

const int MAXN = 26;
class Trie {
private:
    struct Node {
        char c;
        bool isWord;
        Node(char c_, bool isWord_)
            : c(c_)
            , isWord(isWord_)
        {
            for (int i = 0; i < MAXN; ++i)
                children.push_back(NULL);
        };
        vector<Node*> children;
    };
    Node* root;
public: /** Initialize your data structure here. */
    Trie() { root = new Node(‘ ‘, true); } /** Inserts a word into the trie. */
    void insert(string word)
    {
        Node* cur = root;
        for (int i = 0; i < word.size(); ++i) {
            int idx = word[i] – ‘a’;
            if (cur->children[idx] == NULL)
                cur->children[idx] = new Node(word[i], false);
            cur = cur->children[idx];
        }
        cur->isWord = true;
    } /** Returns if the word is in the trie. */
    bool search(string word)
    {
        Node* cur = root;
        for (int i = 0; i < word.size(); ++i) {
            int idx = word[i] – ‘a’;
            if (cur->children[idx] == NULL)
                return false;
            cur = cur->children[idx];
        }
        return cur->isWord;
    } /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix)
    {
        Node* cur = root;
        for (int i = 0; i < prefix.size(); ++i) {
            int idx = prefix[i] – ‘a’;
            if (cur->children[idx] == NULL)
                return false;
            cur = cur->children[idx];
        }
        return true;
    }
};

本代码提交AC，用时118MS。