Interface implemented in terms of single generic locate() method


  • 0
    C

    locate() method which returns TrieNode* always when insert and find/locate the prefix/key on the Trie for other two cases.

    #include <iostream>
    #include <map>
    using namespace std;
    
    class TrieNode {
    public:
      TrieNode(): _valid(false), _links() { }
      bool _valid;
      map<char, TrieNode*> _links; 
    };
    
    
    class Trie {
    public:
      Trie() { root = new TrieNode(); }
    
      inline void insert(string s) {
        locate(s, true)->_valid = true;
      }
    
      inline bool search(string key) {
        TrieNode* nptr = locate(key);
        return nptr ? nptr->_valid: false;
      }
    
      inline bool startsWith(string prefix) {
        TrieNode* nptr = locate(prefix);
        return nptr ? true: false;
      }
      
    private:
      TrieNode* root;
     
      // insert - always returns TrieNode
      // search - returns only if the path found
      TrieNode* locate(string key, bool insert=false) {
        TrieNode* nptr = root;
        for (const char c : key) {
          if (nptr->_links.find(c) == nptr->_links.end()) {
    	    if (insert) {
    	        TrieNode* p = new TrieNode();
    	        nptr->_links[c]= p;
    	        nptr = p;
    	    }
    	    else {
    	        return nullptr;
    	    }
          }
          else {
    	    nptr = nptr->_links[c];
          }
        }
        return nptr;
      }
      
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.