[Leetcode] 208. Implement Trie (Prefix Tree)

Identifying the Problem

Trie Tree를 생성하고, 삽입, 검색, 접두사 검색 (검색엔진의 자동완성) 함수를 구현한다.

Organizing thoughts

Trie에 관한 내용은 아래 블로그를 참고하였다.

[자료구조] 트라이 (Trie) C++ 구현

Sourcecode

##source code 출처

C++, My solution, easy to understand:) - LeetCode Discuss

class TrieNode {
public:
    // TrieNode 객체 생성
    bool finish; //글자의 끝의 유/무 를 finish로 설정
    TrieNode *children[26]; //26개의 자식 노드 생성 ('a~z')
    
    TrieNode() //각 노드의 초기값 설정
    { 
        finish = false;  
        
        for (int i = 0; i < 26; i++)
            children[i] = NULL;
    }//처음 아무것도 없는 상태이므로 각 노드의 끝을 false와 NULL로 설정
};

class Trie {
public:
    Trie() 
    {
        root = new TrieNode(); //Trie 생성
    }

    // 단어를 Trie에 Inserts
    void insert(string word) 
    {
        int word_len = word.length(); //단어의 길이
        int k = 0; //string -> int 알파벳 a~z 를 index로 사용하고자 k = 0~25 로 선언
        TrieNode *cur = root; //탐색노드 cur에 초기 TrieNode 대입
        
        for (int i = 0; i < word_len; i++) //단어의 한 글자씩 Trie 에 추가
        {
            k = word[i] - 'a';
            
            if (cur->children[k] == NULL) 
            {
                cur->children[k] = new TrieNode();
            }////해당 trie가 아무것도 없는 상태라면, 새로 하위 노드 생성
            
            cur = cur->children[k]; //다음 node로 이동
        }
        
        cur->finish = true; //단어의 끝 finish 값을 true로 설정 
    }

    //search 하는 단어가 Trie내에 있다면 true 없다면 false 리턴
    bool search(string word) 
    {
        int word_len = word.length();
        int k = 0;
        TrieNode *cur = root;
        
        for (int i = 0; i < word_len; i++)
        {
            k = word[i] - 'a';
            cur = cur->children[k];
            
            if (cur == NULL)
                return false;
        }
        
        return cur->finish; 
        //insert 글자의 끝 부분을 true로 했을 경우 true 리턴이고 
        //아닐 경우 defalut값이 false이므로 false리턴
    }

    //prefix를 가지는 글자가 있는지 탐색
    bool startsWith(string prefix) 
    {
        int word_len = prefix.length();
        int k = 0;
        TrieNode *cur = root;
        
        for (int i = 0; i < word_len; i++)
        {
            k = prefix[i] - 'a';
            cur = cur->children[k]; //찾는 단어의 글자 순으로 탐색 
            
            if (cur == NULL) //Trie가 NULL이거나, 
                               //탐색할 다음 글자의 node가 NULL인 경우 false return
                return false;
        }
        
        return true; //defalut 값 true
    }

private:
    TrieNode* root; //root 생성
};