###### tags: `Leetcode` `medium` `design` `hash` `python` `c++` `Top 100 Liked Questions`

# 208. Implement Trie (Prefix Tree)

## [題目連結:] https://leetcode.com/problems/implement-trie-prefix-tree/

## 題目:
A **trie** (pronounced as "try") or **prefix tree** is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

* ```Trie()``` Initializes the trie object.
* ```void insert(String word)``` Inserts the string word into the trie.
* ```boolean search(String word)``` Returns ```true``` if the string ```word``` is in the trie (i.e., was inserted before), and ```false``` otherwise.
* ```boolean startsWith(String prefix)``` Returns ```true``` if there is a previously inserted string ```word``` that has the prefix ```prefix```, and ```false``` otherwise.


## 解題想法:
* 題目為實作字典樹(前綴樹)
* 字典樹的每一個node皆是map:
* key: 當前字母
* val: map，所有與當前字母有關聯的下個字母
* **若當前字母為某單詞的結尾，則在其val中新增一個key為"#"**

* 示意說明如下:

* 根節點為dict，裡面存的每個char也都為dict
想法:
insert:  a , ant , cat , and (尾部加上#表示為完整單詞)

則當search 'an'時:
因為 key 'n'的map裡面只有{t,d}沒有'#'，
因此沒有該an單字 -> return False

再insert 單詞'an'時:
由於前面有'an'了 
因此只要在n後面加上'#'即可

下次再search 'an'時 
後面有'#' 
所以就return True了

則:   root:   {  a       c }
                /         \
             { n '#' }    { a }
              /  \          \
           { t    d }      { t }
            /      \          \
          {'#'}    {'#'}     {'#'}

* 同類型題目:[211. Design Add and Search Words Data Structure](/llmwVvuqQdKNXizscN4tMQ)

## Python:

class Trie(object):

    def __init__(self):
        self.root={} #根節點為dict，裡面存的每個char也都為dict

    def insert(self, word):
        """
        :type word: str
        :rtype: None
        """
        curMap=self.root
        for char in word:
            #給該char建立下一層dict
            if char not in curMap:
                curMap[char]={}
            #移到下一層找下個char
            curMap=curMap[char]
        #當字串結束 最後加上'#'
        curMap['#']=True

    def search(self, word):
        """
        :type word: str
        :rtype: bool
        """
        curMap=self.root
        for char in word:
            if char not in curMap:
                return False
            #若出現 則繼續往下層找
            curMap=curMap[char]
        return True if '#' in curMap else False

    def startsWith(self, prefix):
        """
        :type prefix: str
        :rtype: bool
        """
        #此功能為: 是否存在以prefix為開頭的字串
        curMap=self.root
        for char in prefix:
            if char not in curMap:
                return False
            curMap=curMap[char]
        return True

result = Trie()
result.insert('a')
result.insert('ant')
result.insert('cat')
result.insert('and')
print(result.search('an')) #Fasle
result.insert('an')
print(result.search('an')) #True
print(result.startsWith('ca'))  #True

## C++:
* 額外寫個TrieNode
* 總共就26個字母: 指針數組

#include<bits/stdc++.h>
using namespace std;

class TrieNode{
public:
    TrieNode* childMap[26];
    bool wordEnd;
    //Constructor
    TrieNode(): wordEnd(false) {
        for (auto& child: childMap) child=nullptr;
    }
};

class Trie{
public:
    Trie(){
        root=new TrieNode();
    }

    void insert(string word){
        TrieNode* curMap=root;
        for (char val: word){
            int num=val-'a';
            if (!curMap->childMap[num])
                curMap->childMap[num]=new TrieNode();
            curMap=curMap->childMap[num];
        }
        curMap->wordEnd=true;
    }

    bool search(string word){
        TrieNode* curMap=root;
        for (char val: word){
            int num=val-'a';
            if (!curMap->childMap[num])
                return false;
            curMap=curMap->childMap[num];
        }
        return curMap->wordEnd;
    }

    bool startsWith(string prefix){
        TrieNode* curMap=root;
        for (char val: prefix){
            int num=val-'a';
            if (!curMap->childMap[num])
                return false;
            curMap=curMap->childMap[num];
        }
        return true;
    }

private:
    TrieNode *root;
};

int main(){
    Trie* res=new Trie();
    res->insert("a");
    res->insert("ant");
    res->insert("cat");
    res->insert("and");
    bool test1=res->search("an");
    bool test2=res->startsWith("an");
    cout<<test1<<" ,"<<test2<<endl; // 0(false),1(true)
    return 0;
}