208 Implement Trie (Prefix Tree)

来源：Leetcode

原帖：https://leetcode.com/problems/implement-trie-prefix-tree/

题目：
Implement a trie with insert, search, and startsWith methods.


代码：

 class TrieNode {  
 public:  
   // Initialize your data structure here.  
   TrieNode(bool word = false) {  
     isWord = word;  
   }  
   bool isWord;  
   unordered_map<char,TrieNode*> next;  
 };  
   
 class Trie {  
 public:  
   Trie() {  
     root = new TrieNode();  
   }  
   
   // Inserts a word into the trie.  
   void insert(string s) {  
     TrieNode* cur = root;  
     for (int i = 0; i < s.size(); ++i) {  
       if (!cur->next.count(s[i])) {  
         cur->next[s[i]] = new TrieNode();  
       }  
       cur = cur->next[s[i]];  
       if (i == s.size()-1) cur->isWord = true;  
     }  
   }  
   
   // Returns if the word is in the trie.  
   bool search(string key) {  
     if (key.empty()) return false;  
     TrieNode* cur = root;  
     for (int i = 0; i < key.size(); ++i) {  
       if (!cur->next.count(key[i]))   
         return false;  
       cur = cur->next[key[i]];  
     }  
     return cur->isWord ? true : false;  
   }  
   
   // Returns if there is any word in the trie  
   // that starts with the given prefix.  
   bool startsWith(string prefix) {  
     if (prefix.empty()) return false;  
     TrieNode* cur = root;  
     for (int i = 0; i < prefix.size(); ++i) {  
       if (!cur->next.count(prefix[i]))   
         return false;  
       cur = cur->next[prefix[i]];  
     }  
     return true;  
   }  
   
 private:  
   TrieNode* root;  
 };  
   
 // Your Trie object will be instantiated and called as such:  
 // Trie trie;  
 // trie.insert("somestring");  
 // trie.search("key");  

扩展问题：

 /*  
  Shortest Unique Prefix *  
  Trie node  
  Given a string s and a set of strings D, find the shortest prefix of s   
  which is not a prefix of any string in D.  
  Example:  
  If s = "cat" and D = {"dog", "be", "cut"} return "ca"  
  If s = "cat" and D = {"dog", "be", "cut", "car"} return "cat"  
  If s = "cat" and D = {"dog", "be", "cut", "car", "cat"} return \epsilon   
 */  
   
 struct TrieNode {  
   bool isString;  
   unordered_map<char, TrieNode*> next; // TreeNode* hash[26];  
   TrieNode(bool _isString = false) : isStirng(_isString) {}  
 };  
   
 class Trie {  
 private:  
  TrieNode* root;  
   
 public:  
  Trie() {  
   root = new TrieNode();  
  }  
   
  bool insert(const string& s) {  
   TrieNode* p = root;  
   for (const char &c : s) {  
    if (p->next.find(c) == p->next.end()) {  
     p->next[c] = new TrieNode(false);  
    }  
    p = p->next[c];  
   }  
   // s already existed in this trie  
   if (p->isString == true) {  
    return false;  
   } else { // p->isString == false  
    p->isString = true; // inserts s into this trie  
    return true;  
      }  
  }  
   
  string getShortestUniquePrefix(const string& s) {  
   TrieNode* p = root;  
   string prefix = "";  
   for (auto& c : s) {  
    prefix += c;  
    if (p->next.find(c) == p->next.end()) {  
     return prefix;  
    }  
    p = p->next[c];  
   }  
   return "";   
  }  
 };  
   
   
 string find_shortest_prefix(const string& s, const unordered_set<string>& D) {  
  // Build a trie according to given dictionary D  
  Trie T;  
  for (const string &world : D) {  
   T.insert(world);  
  }  
  return T.getShortestUniquePrefix(s);  
 }