[Algorithm][Leetcode] 208. Implement Trie (Prefix Tree)

Trie를 c++로 구현해봤다.

 

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

• 트라이(Trie) : 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다.
• 자식으로 a-z까지 TreeNode들과 문자의 끝을 표시하는 end flag를 갖는다.

class TrieNode {
private:
    bool endFlag;
    TrieNode* next[27 + 'a'];
public:
    TrieNode() {
        endFlag = false;
        memset(next, NULL, sizeof(next));
    }

    TrieNode* getNext(char c) {
        return next[c];
    }

    void setNext(char c) {
        next[c] = new TrieNode();
        // setEndFlag(false);
    }

    bool getEndFlag() {
        return endFlag;
    }

    void setEndFlag(bool endFlag) {
        this->endFlag = endFlag;
    }
};

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

    void insert(string word) {
        TrieNode* node = root;
        for (char c : word) {
            if (node->getNext(c)) {
            }
            else {
                node->setNext(c);
            }
            node = node->getNext(c);
        }
        node->setEndFlag(true);
    }

    bool search(string word) {
        TrieNode* node = root;
        for (char c : word) {
            if (node->getNext(c)) {
                node = node->getNext(c);
            }
            else {
                return false;
            }
        }
        return node->getEndFlag();
    }

    bool startsWith(string prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            if (node->getNext(c)) {
                node = node->getNext(c);
            }
            else {
                return false;
            }
        }
        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);
 */