首页 > 其他 > 详细

【62】208. Implement Trie (Prefix Tree)

时间:2017-02-12 17:03:31      阅读:123      评论:0      收藏:0      [点我收藏+]

208. Implement Trie (Prefix Tree)

Description Submission Solutions Add to List

  • Total Accepted: 63834
  • Total Submissions: 245645
  • Difficulty: Medium
  • Contributors: Admin

 

Implement a trie with insertsearch, and startsWith methods.

Note:
You may assume that all inputs are consist of lowercase letters a-z.\

 

class TrieNode{
    public:
        bool isWord;
        TrieNode* child[26];
        TrieNode() : isWord(false){
            for(auto &a : child){//更改内容要用&
                a = NULL;
                
            }
        }  
};

class Trie {
public:
    /** Initialize your data structure here. */
    Trie() {
        root = new TrieNode();
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        TrieNode* p = root;
        for(char c : word){
            int i = c - a;
            if(p -> child[i] == NULL){
                p -> child[i] = new TrieNode();
            }
            p = p -> child[i];
        }
        p -> isWord = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        TrieNode* p = root;
        for(char c : word){
            int i = c - a;
            if(!p -> child[i]) return false;
            p = p -> child[i];
        }
        //if(!p -> isWord) return false;
        //return true;
        return p -> isWord;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        TrieNode* p = root;
        for(char c : prefix){
            int i = c - a;
            if(!p -> child[i]) return false;
            p = p -> child[i];
        }
        //if(!p -> isWord) return false;
        return true;
        //return p -> isWord;
    }
private:
    TrieNode* root;
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * bool param_2 = obj.search(word);
 * bool param_3 = obj.startsWith(prefix);
 */

 

 

 

 

【62】208. Implement Trie (Prefix Tree)

原文:http://www.cnblogs.com/93scarlett/p/6391087.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!