208. Implement Trie (Prefix Tree)

解題思路

先自定義 node，用 pointer 的方式連接。檢查 node 是否已經是字的結尾，就用 bool 來記錄。

程式碼

class Node{
public:
    bool isEnd;
    Node* child[26];
    Node()
    {
        isEnd = false;
        for(int i=0; i<26; i++)
            child[i] = nullptr;
    }
};
class Trie {
public:
    Node* root = new Node();

    Trie() {
    }
    
    void insert(string word) {
        Node* current = root;
        for(int i=0; i<word.size(); i++)
        {
            if(current->child[word[i] - 'a'] == nullptr)
                current->child[word[i] - 'a'] = new Node();
            current = current->child[word[i] - 'a'];
        }
        current->isEnd = true;
    }
    
    bool search(string word) {
        Node* current = root;
        for(int i=0; i<word.size(); i++)
        {
            if(current->child[word[i] - 'a'] == nullptr)
                return false;
            current = current->child[word[i] - 'a'];
        }
        return current->isEnd == true;
    }
    
    bool startsWith(string prefix) {
        Node* current = root;
        for(int i=0; i<prefix.size(); i++)
        {
            if(current->child[prefix[i] - 'a'] == nullptr)
                return false;
            current = current->child[prefix[i] - 'a'];
        }
        return true;
    }
};