NO CODING NO LIFE: LeetCode: Implement Trie(Prefix Tree)

Tries:
For TrieNode(), array is used to store next nodes address.

insert(): jump to the next node according to char of string.
NOTE: If I want to get the the address of a pointer, I have to use pointers to pointers.(二级指针）
<way 1> judge the next node is null or not, if null, create a new one.
<way 2> judge the current pointer is null or not, if null, create a new one. (use pointers to pointers here, since we need to store the address of the current pointer to create a new node. If we store the current pointer directly when the current pointer is null, then we will lost the address to create a new node). This way is too complex and not necessary, and I write it for fun.
Cannot use & reference here, since the nature of reference is a constant pointer to pointer. That's why reference has to be initialized when created.

void insert(string word) {
        TrieNode** curNode = &root;
        for(int i=0; i < word.size(); i++){
            int pos = word[i]-'a';
            if(*curNode == NULL) *curNode = new TrieNode();
            curNode = &((*curNode)->children[pos]);
        }
        if(*curNode == NULL) {
   *curNode = new TrieNode();
        }
        if((*curNode)->val == false) {
   (*curNode)->val = true;
        }
    }

search(): similar to insert except when the node is null, return false.

startsWith(string prefix): similar to search for prefix. If all nodes for prefix exist, then we need to traverse all sub nodes after prefix. I used BFS to traverse the end of prefix and all sub nodes to make sure at lease one sub node has value of true.
Here, if only prefix exist is ok. e.g. insert("a") starsWith("a") should return true.

~Trie() delete itself recursively

class TrieNode {
public:
    // Initialize your data structure here.
    bool val;
    TrieNode* children[26];
    TrieNode() {
        val=false;
        for(int i=0; i<26; i++){
            children[i]=NULL;
        }
    }
    void Delete(){
        for(int i = 0; i < 26; i++){
            if(children[i] != NULL) children[i]->Delete();
        }
        delete this;
    }
};

class Trie {
public:
    Trie() {
        root = new TrieNode();
    }
    ~Trie(){
        if(root != NULL) root->Delete();
    }
    // Inserts a word into the trie.
   void insert(string word) {
        TrieNode* curNode = root;
        for(int i = 0; i < word.size(); i++){
            int pos = word[i]-'a';
            if(curNode->children[pos] == NULL) curNode->children[pos] = new TrieNode();
            curNode = curNode->children[pos];
        }
        if(curNode->val == false) curNode->val = true;
    }
    
    // Returns if the word is in the trie.
    bool search(string word) {
        TrieNode* curNode = root;
        for(int i = 0; i < word.size(); i++){
            int pos=word[i]-'a';
            if(curNode == NULL) {
    return false;
      }
            curNode = curNode->children[pos];
        }
        if(curNode == NULL) {
   return false;   
        }
        return curNode->val;
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    bool startsWith(string prefix) {
        TrieNode* curNode = root;
        for(int i = 0; i < prefix.size(); i++){
            int pos = prefix[i] - 'a';
            if(curNode == NULL) return false;
            curNode = curNode->children[pos];
        }
        if(curNode == NULL) return false;
        queue<TrieNode*> q;
        q.push(curNode);
        while(!q.empty()){
            TrieNode* cur = q.front();
            q.pop();
            if(cur->val == true) return true;
            for(int i = 0; i < 26; i++){
                if(cur->children[i] != NULL) q.push(cur->children[i]);
            }
        }
        return false;
    }

private:
    TrieNode* root;
};

Analysis:
Speed is just at the average level. Optimization is needed.
(1) startswith():
For a trie without deletion operation, we only need to traverse nodes corresponding string prefix regardless of val. So I rewrite this function. It is almost same with search() without judgement of value.

bool startsWith(string prefix){
         TrieNode* curNode = root;
         int len = prefix.size();
         for(int i=0; i<len; i++){
             int pos=prefix[i]-'a';
             if(!curNode->children[pos]) return false;
             curNode = curNode->children[pos];
         }
         return true;
     }

(2) the destructor I wrote also take a long time. After deletion. speed is much better.

Reference:
百科pointers to pointers
How to get address from an array
Interesting understand of &
destructor for Trie
Yu's garden for optimization

NO CODING NO LIFE

2015年7月13日星期一

LeetCode: Implement Trie(Prefix Tree)

没有评论:

发表评论