Trie

정의

참고: 위키백과

Trie(트라이)는 탐색 트리의 일종이다. 주로 문자열이 키인 경우가 많다.

트라이는 우리에게 아주 친숙하다. 구글의 자동 완성 기능과 같이 필요한 글자를 저장하는 것이 일반적인 응용 가운데 하나이다. 트라이에서 빠르게 조회, 삽입, 삭제할 수 있는 기능을 활용하는 응용이다.

시간 복잡도

트라이는 탐색과 삽입을 지원하는 노드로 구성된 트리이다.
키의 길이가 m일 때 탐색과 삽입 모두 O(m) 시간에 수행된다.

예제 - 720. Longest Word in Dictionary

트라이를 사용하면 leetcode의 720번과 같은 문제를 풀수 있다.
한 글자씩 붙여서 만들 수 있는 단어 중 가장 긴 단어를 리턴하면 되는 문제다.

Return the longest word in words that can be built one character at a time by other words in words.

TrieNode struct 생성

문제를 풀기 위한 TrieNode 구조체(또는 클래스)를 먼저 생성한다.
클래스 씩이나 갖고있어야 하는 이유는 한 char가 다음 char를 연결하고 있어야 하기 때문이다.
예를 들어, apple라는 string을 삽입한다. 그러면 a, p, p, l, e는 각각의 TriNode 구조체를 생성하고 a -> p -> p -> l -> e 로 연결되어 연결되어 있다.

root -> a -> p -> p -> l -> e

그 후에 apps 가 삽입되었다고 하면, 이렇게 될 것이다.

root -> a -> p -> p -> l -> e
 		          └--> s

그 다음에 ban라는 string을 삽입한다면,

root -> a -> p -> p -> l -> e
 		          └--> s
  └---> b -> a -> n

이렇게 된다.

struct TrieNode {
    TrieNode* node[26];
    // bool end;
    TrieNode() {
        memset(node, 0, sizeof(node));
        // end = false;
    }
    
    void insert(char val) {
        node[val-'a'] = new TrieNode();
    }
    
    bool search(char val) {
        return node[val-'a'] == nullptr ? false : true;
    }
    
    TrieNode* getNext(char val) {
        return node[val-'a'];
    }
};

• 내가 class로 하지 않고 struct로 구현한 이유는 기본적으로 struct 내 변수나 함수들을 public으로 선언해서 struct 밖에서 직접 접근하려 했기 때문이다. (문제풀이다 보니 보안 보다는 편의를 위해..;)
• lowercase English letters 만 저장할 것이므로 (이 문제의 조건) 26개의 알파벳을 각각 저장할 수 있는 node[26]처럼 array를 선언했다.
• bool end를 주석처리 한 이유는 현재 문제에서는 마지막을 표시할 필요가 없기 때문이다.
  보통은 string 하나를 넣을때 마지막 문자임을 표현해준다.
• 개인적인 기호에 의해 insert 함수에서는 새로운 노드까지 만들어준다.
• getNext 함수는 다음 char 을 가르키기 위한 함수이다.

전체 코드

struct TrieNode {
    TrieNode* node[26];
    // bool end;
    TrieNode() {
        memset(node, 0, sizeof(node));
        // end = false;
    }
    
    void insert(char val) {
        node[val-'a'] = new TrieNode();
    }
    
    bool search(char val) {
        return node[val-'a'] == nullptr ? false : true;
    }
    
    TrieNode* getNext(char val) {
        return node[val-'a'];
    }
};

class Solution {
public:
    TrieNode* root;
    string ans;
    
    string longestWord(vector<string>& words) {
        root = new TrieNode();
        sort(words.begin(), words.end());
        
        for (int i = 0; i < words.size(); i++) {
            insert(words[i]);
        }
        return ans;
    }
    
    void insert(string s) {
        TrieNode* ptr = root;
        for (int i = 0; i < s.size(); i++) {
            if (ptr->search(s[i]) == false) {
                if (i == s.size()-1) {
                    ptr->insert(s[i]);
                    if (ans.size() < s.size()) {
                        ans = s;
                    }
                }
                else {
                    return;
                }
            }
            ptr = ptr->getNext(s[i]);
        }
        // ptr->end = true;
    }
};