ksh021144

ksh021144

Learn more, Do more.

[LeetCode] 208. Implement Trie (Prefix Tree)

3 분 소요

LeetCode - 208. Implement Trie (Prefix Tree) 알고리즘 문제 풀이

분류

문제 링크 : https://leetcode.com/problems/implement-trie-prefix-tree/

풀이

Trie 자료 구조를 구현하는 문제이다.

insert

소문자 - 'a' 값을 인덱스로 활용하여 해당 위치가 nullptr이면 동적 할당을 해주었고, 동적 할당된 위치에 대해 지속적으로 노드를 생성해나가는 구조로 작성하였다.

word를 구성하는 마지막 알파벳까지 노드를 생성했으면 이때의 endPoint를 true로 변경하고 함수를 종료한다.

insert 멤버 함수에 디폴트 매개변수를 추가하여 재귀적으로 호출될 수 있도록 코드를 변경하기는 했는데, 원래 insert 멤버 함수의 시그니처가 void insert(string word)라는 것을 감안하면 반복문 기반으로 노드를 생성하는 것을 원했던 것 같기는 하다. 그래서 반복문 기반으로 동작하는 insert 함수는 따로 주석으로 넣어두었다.

search 함수는 insert 함수를 통해 추가되었던 문자열과 정확히 일치하는 문자열이 있는지 검사하는 함수이다.

Trie 자료구조에서 찾으려는 문자열(word)을 이루는 모든 노드가 생성되어 있는지 검사한다.

  • 할당되지 않은 위치를 가리키는 노드가 있다면 false를 반환한다.
  • 가장 마지막 위치에 도달하면 true가 아니라 now->endPoint의 값을 반환한다.

now->endPoint 값을 반환하는 이유는 입력 예제가 아래와 같을 때, “apple”의 입력을 “app”이 입력된 것으로 오인하지 않기 위해서이다. (“app”이 입력된적은 없으므로, 마지막 now->endPoint 값은 false이다.)

Trie* trie = new Trie();
trie->insert("apple");
cout << trie->search("app"); // 0 (false)

startsWith

startsWith 함수는, 이 함수의 매개변수로 시작하는 문자열이 존재하는지 검사하는 함수이다.

Trie 자료구조에서 노드를 검사하는 로직은 위의 search 함수와 동일하다.

  • 할당되지 않은 위치를 가리키는 노드가 있다면 false를 반환한다.
  • 그러한 노드가 없다면 최종적으로 true를 반환한다.

따라서 아래의 코드에서 trie->startsWith("app");의 결과는 1 (true)이 된다.

Trie* trie = new Trie();
trie->insert("apple");
cout << trie->startsWith("app"); // 1 (true)

소스 코드

class Trie {
    bool endPoint;
    Trie* node[26];

public:
    /** Initialize your data structure here. */
    Trie() {
        endPoint = false;
        fill(node, node + 26, nullptr);
    }

    /** Inserts a word into the trie. */
    // recursive based
    void insert(const string& word, int idx = 0) {
        if (word[idx] == '\0') {
            endPoint = true;
            return;
        }
        int x = word[idx] - 'a';
        if (node[x] == nullptr) {
            node[x] = new Trie();
        }
        node[x]->insert(word, idx + 1);
    }

    // for-loop based
    //void insert(const string& word) {
    //    int idx = word[0] - 'a';
    //    if (node[idx] == nullptr) {
    //        node[idx] = new Trie();
    //    }
    //    Trie* now = node[idx];
    //    for (int i = 1; i != word.length(); ++i) {
    //        int nextIdx = word[i] - 'a';
    //        if (now->node[nextIdx] == nullptr) {
    //            now->node[nextIdx] = new Trie();
    //        }
    //        now = now->node[nextIdx];
    //    }
    //    now->endPoint = true;
    //}

    /** Returns if the word is in the trie. */
    bool search(const string& word) {
        int idx = word[0] - 'a';
        Trie* now = node[idx];
        if (now == nullptr) return false;

        for (int i = 1; i != word.length(); ++i) {
            idx = word[i] - 'a';
            now = now->node[idx];
            if (now == nullptr) {
                return false;
            }
        }
        return now->endPoint;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(const string& prefix) {
        int idx = prefix[0] - 'a';
        Trie* now = node[idx];
        if (now == nullptr) return false;

        for (int i = 1; i != prefix.length(); ++i) {
            idx = prefix[i] - 'a';
            now = now->node[idx];
            if (now == nullptr) {
                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);
 */

insert 함수의 경우, 재귀 구조로 작동하는 코드보다 반복문 기반으로 작동하는 코드의 실행 속도가 좀 더 빠를 것 같았는데, 재귀 구조로 작동하는 코드가 미묘하게 빨랐다. 반복문 기반의 코드도 사용한 메모리 수치는 똑같지만 효율이 좀 더 좋게 나온 것은 재귀 호출에 필요한 스택 메모리를 사용하지 않아서 그런 것 같다.

재귀 기반

Runtime: 44 ms, faster than 98.80% of C++ online submissions for Implement Trie (Prefix Tree).
Memory Usage: 45 MB, less than 59.81% of C++ online submissions for Implement Trie (Prefix Tree).

반복문 기반

Runtime: 52 ms, faster than 94.00% of C++ online submissions for Implement Trie (Prefix Tree).
Memory Usage: 45 MB, less than 69.78% of C++ online submissions for Implement Trie (Prefix Tree).

참고