[Trie][Medium] 208. Implement Trie (Prefix Tree)

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

LeetCode - The World's Leading Online Programming Learning Platform

 

Q. Trie class를 insert(), search(), startsWith()와 함께 구현하라. 

 

 

Solution. 

 우선 Trie 자료 구조에 대해서 좀 정리 해 보자. 

 Trie는 문자 정리를 위해서 만든 tree의 한 일환인 자료 구조로, 트라이 라고 읽는다. 

 

   위와 같이 한 노드가 하나의 문자를 저장하며, branch에 따라서 문자열을 저장하는 구조이다. 

   따라서 검색 시 속도가 빠르지만, 메모리를 필수적으로 많이 쓴다. 

   또한 겹쳐지는 문자가 생기므로, 그 끝을 별도로 기록할 필요가 있다.   

 

 

   위 논리대로 코드를 작성해 본다. 

class Trie {

private:
    struct Node
    {
        char key;
        bool fin;
        vector<Node*> children;
        Node(char inKey, bool inFin)
        {
            key = inKey;	fin = inFin;
        }
    };

    Node* mRoot;
    Node* FindNode(char key, Node* target)
    {
        for (int q = 0; q < target->children.size(); ++q)
        {
            if (target->children[q]->key == key)
                return target->children[q];
        }
        return NULL;
    }
    
public:

    Trie() {
        mRoot = new Node(' ', false);
    }

    void insert(string word) 
    {
        Node* cur = mRoot;
        for (int idx = 0; idx < word.size(); ++idx)
        {
            Node* found = FindNode(word[idx], cur);
            bool isLastChar = idx == word.size() - 1;
            if (found == NULL)
            {
                found = new Node(word[idx], isLastChar);
                cur->children.push_back(found);
            }
            else
                found->fin = isLastChar ? true : found->fin;

            cur = found;
        }
    }
    
    bool search(string word) 
    {
        Node* cur = mRoot;
        for (int idx = 0; idx < word.size(); ++idx)
        {
            Node* found = FindNode(word[idx], cur);
            if (found == NULL)	return false;
            
            bool isLastChar = idx == word.size() - 1;
            if (isLastChar && found->fin)
                return true;

            cur = found;
        }
        return false;
    }
    
    bool startsWith(string prefix) 
    {
        Node* cur = mRoot;
        for (int idx = 0; idx < prefix.size(); ++idx)
        {
            Node* found = FindNode(prefix[idx], cur);
            if (found == NULL)	return false;

            if (idx == prefix.size() - 1)
                return true;

            cur = found;
        }
        return false;
    }
};

 

 

자료구조의 정의를 제대로 이해하고 있다면 구현 자체는 큰 문제가 없을 것으로 생각한다.