# 【LeetCode】 208. Implement Trie (Prefix Tree)

## Description
> Implement a trie with `insert`, `search`, and `startsWith` methods.

> Note:
> * You may assume that all inputs are consist of lowercase letters `a-z`.
> * All inputs are guaranteed to be non-empty strings.

> 實作一個字典樹包含`insert`、`search`和`startsWith`等方法。

> 提示：
> * 你可以假設所有的輸入都只會包含小寫英文字母`a-z`。
> * 所有輸入都保證不會是空字串。

## 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

## Solution

* 這一題要實作資料結構中的字典樹，不知道是什麼的可以參照[wiki](https://zh.wikipedia.org/wiki/Trie)。
* 簡單來說它就是一棵樹，每個節點底下有`a~z`共`26`個子節點。
* 每次要新增單字進去的時候，就依序把每個字母對應的節點加進去，最後在單字結束的地方做個標記。
* 假設加入`abc`，就依序新增`a->b->c`三個節點(注意，他們是父子關係)，並在`c`節點加上標記。
* 查詢的時候就去檢查單字的字母對應的節點是否存在，並且確認結束點有沒有標記。
* 如果沒有檢查標記，那上面加入`abc`的時候，因為`a->b`節點都存在，就會誤判`ab`也曾加入過。
* 而檢查前序字串就不需檢查標記，其餘都和查詢一樣。

---
* 解題歸解題，可以仔細想想這樣的結構有什麼好處？
* 既然都叫做字典樹，那我們就拿字典來舉例。
* 試想今天你需要儲存一個字典量的單字，並且要有查詢功能。如果單純使用`string[]`或是`vector<string>`去儲存，那麼我們就需要大量的空間。
* 字典樹的好處在於可以有效壓縮需要的儲存空間，因為如果有單字前面相同，相同的部分都不需要額外的空間。
* 舉個例子：如果你已經建立了`apple`，因為`app`節點已經存在，所以只需要加上標記而不用其他動作。

### Code

class Trie {
public:
    bool isWord;
    Trie* node[26];	//Next letter's node.
    
    /** Initialize your data structure here. */
    Trie() {
        isWord = false;
        for(int i = 0; i < 26; i++)
            this->node[i] = NULL;
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        if(word.empty())
        {
            this->isWord = true;
            return;
        }
        if(!this->node[word.front() - 'a'])
        {
            this->node[word.front() - 'a'] = new Trie;
        }
        this->node[word.front() - 'a']->insert(word.substr(1));
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        if(word.empty())
            return this->isWord;
        
        if(!this->node[word.front() - 'a'])
            return false;
        
        return this->node[word.front() - 'a']->search(word.substr(1));
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        if(prefix.empty())
            return true;
        
        if(!this->node[prefix.front() - 'a'])
            return false;
        
        return this->node[prefix.front() - 'a']->startsWith(prefix.substr(1));
    }
};

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

###### tags: `LeetCode` `C++`