【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。
• 簡單來說它就是一棵樹，每個節點底下有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++