LeetCode- Implement Trie (Prefix Tree)

题目：

Implement a trie with insert, search, and startsWith methods.

Example:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");   
trie.search("app");     // returns true

Note:

• You may assume that all inputs are consist of lowercase letters a-z.
• All inputs are guaranteed to be non-empty strings.

实现：

      TrieTree是一个多叉树，是解决字符串快速匹配问题的数据结构，  他用于存储一个字符串，每个TrieTree的节点代表一个字符串/字符串前缀，每个节点可以有多个孩子节点，指向不同子节点不同路径代表不同的字符串，子节点的字符串是由本子节点的字符加上从根节点到本节点路径上的字符组成。 

     本地实现上， 节点的子节点使用数组或哈希表存储，只处理26个字母，通过判断子节点指针是否为空判断该字符是否存在。 具体实现参考leetcode提供的伪代码

•    使用数组版本

class Trie {
private:
    #define N 26
    struct TrieNode {
        TrieNode* children[N];
        bool bEnd=false;
    };
    TrieNode *root;

    
public:
       
    /** Initialize your data structure here. */
    Trie() {
        root = new TrieNode;
        for (int i=0; i<N; i++){
            root->children[i]= nullptr;
        }
        
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
    /*
      1. Initialize: cur = root
      2. for each char c in target string S:
      3.      if cur does not have a child c:
      4.          cur.children[c] = new Trie node
      5.      cur = cur.children[c]
      6. cur is the node which represents the string S
    */
        
    //  Return a specific child node with char c: (root->children)[c - 'a']

      TrieNode *cur = root;
    
      for(char& c : word) {
        if (cur->children[c - 'a'] == nullptr){
            cur->children[c - 'a'] = new TrieNode();
        }
        cur = cur->children[c - 'a'];
      }
      cur->bEnd = true;
        
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
    /*1. Initialize: cur = root
      2. for each char c in target string S:
      3.      if cur does not have a child c:
      4.          search fails
      5.      cur = cur.children[c]
      6. search successes
    */
        
      TrieNode *cur = root;
      for(char& c : word) {
        if (cur->children[c - 'a'] == nullptr){
           return false;
        }
        cur = cur->children[c - 'a'];
      } 
      
      if (cur->bEnd)
        return true;
      else 
        return false;
        
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
    /*1. Initialize: cur = root
      2. for each char c in target string S:
      3.      if cur does not have a child c:
      4.          search fails
      5.      cur = cur.children[c]
      6. search successes
    */
      TrieNode *cur = root;
      for(char& c : prefix) {
        if (cur->children[c - 'a'] == nullptr){
           return false;
        }
        cur = cur->children[c - 'a'];
      } 
      
      return true;
        
    }
};

/**
 * 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);
 */

• 使用hash表实现

class Trie {
private:
    #define N 26
    struct TrieNode {
         unordered_map<char, TrieNode*> children;
         bool bEnd=false;
    };
    TrieNode *root;

public:
       
    /** Initialize your data structure here. */
    Trie() {
        root = new TrieNode;
        for (int i=0; i<N; i++){
             ( root->children)[i]= nullptr;
        }
        
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
    /*
      1. Initialize: cur = root
      2. for each char c in target string S:
      3.      if cur does not have a child c:
      4.          cur.children[c] = new Trie node
      5.      cur = cur.children[c]
      6. cur is the node which represents the string S
    */
        
     //  unordered_map  char c: (root->children)[c]

      TrieNode *cur = root;
    
      for(char& c : word) {

        if ((cur->children)[c] == nullptr){
            (cur->children)[c] = new TrieNode();
        }
        cur = (cur->children)[c];
      }
      cur->bEnd = true;
        
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
    /*1. Initialize: cur = root
      2. for each char c in target string S:
      3.      if cur does not have a child c:
      4.          search fails
      5.      cur = cur.children[c]
      6. search successes
    */
        
      TrieNode *cur = root;
      for(char& c : word) {
          if ((cur->children)[c] == nullptr){
            return false;
          }
        cur = (cur->children)[c];
      }
      if (cur->bEnd)
        return true;
      else 
        return false;
        
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
    /*1. Initialize: cur = root
      2. for each char c in target string S:
      3.      if cur does not have a child c:
      4.          search fails
      5.      cur = cur.children[c]
      6. search successes
    */
      TrieNode *cur = root;
      for(char& c : prefix) {
        if ((cur->children)[c] == nullptr){
            return false;
          }
        cur = (cur->children)[c];
     
      } 
      
      return true;
        
    }
};

/**
 * 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);
 */

参考：

https://leetcode.com/problems/implement-trie-prefix-tree/solution/