美文网首页
LeetCode 208-Implement Trie (Pre

LeetCode 208-Implement Trie (Pre

作者: 胡哈哈哈 | 来源:发表于2016-05-21 11:21 被阅读42次

    Implement a trie with insert, search, and startsWith methods.
    Note:
    You may assume that all inputs are consist of lowercase letters a-z.

    题意

    实现一个字典树,包含插入、查找和前缀查找功能。所有的输入都是小写字母a-z。

    分析

    就是一个正常的字典树实现,每个节点包含26个指向孩子节点的指针,和标识字典中单词结尾的isTail标识。初始化时26个指针child[i]NULLisTailfalse

    注意

    • startsWith(prefix)方法不需要待检查的prefix是字典树中单词的结尾;
    • search(key)方法要求待检查key是字典树中单词的结尾;
    • 对指针数组的声明应该是TrieNode *child[26]

    AC代码

    class TrieNode {
    public:
        // Initialize your data structure here.
        TrieNode() {
            for (int i = 0; i != 26; ++i) {
                child[i] = NULL;
                isTail = false;
            }
        }
        TrieNode *child[26];
        bool isTail;
    };
    
    class Trie {
    public:
        Trie() {
            root = new TrieNode();
        }
    
        // Inserts a word into the trie.
        void insert(string s) {
            TrieNode *curr = root;
            for (int i = 0; i != s.size(); ++i) {
                int index = find(s[i]);
                if (!curr->child[index]) {
                    curr->child[index] = new TrieNode();
                }
                curr = curr->child[index];
            }
            curr->isTail = true;
        }
    
        // Returns if the word is in the trie.
        bool search(string key) {
            TrieNode *curr = root;
            for (int i = 0; i != key.size(); ++i) {
                int index = find(key[i]);
                if (!curr->child[index]) return false;
                curr = curr->child[index];
            }
            if (!curr->isTail) return false;
            return true;
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        bool startsWith(string prefix) {
            TrieNode *curr = root;
            for (int i = 0; i != prefix.size(); ++i) {
                int index = find(prefix[i]);
                if (!curr->child[index]) return false;
                curr = curr->child[index];
            }
            return true;
        }
    
    private:
        TrieNode* root;
        int find(char ch) { return ch - 'a'; }
    };
    
    // Your Trie object will be instantiated and called as such:
    // Trie trie;
    // trie.insert("somestring");
    // trie.search("key");
    

    相关文章

      网友评论

          本文标题:LeetCode 208-Implement Trie (Pre

          本文链接:https://www.haomeiwen.com/subject/xstorttx.html