[Leetcode] 208. Implement Trie (Prefix Tree) 문제 풀이

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

Implement Trie (Prefix Tree) - LeetCode

 

문제 내용

Trie 구현

 

Example 1:

Input

["Trie", "insert", "search", "search", "startsWith", "insert", "search"]

[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

Output [null, null, true, false, true, null, true]

Explanation

Trie trie = new Trie();

trie.insert("apple");

trie.search("apple"); // return True

trie.search("app"); // return False

trie.startsWith("app"); // return True

trie.insert("app");

trie.search("app"); // return True

 

문제 풀이

Trie를 구현하면 된다.

startWith는 주어진 prefix를 다 탐색할때까지 Trie에 존재하면 true이다.

class Trie {
public:
    Trie* table[26] = {nullptr};
    bool isFinish = false;
    
    Trie() {
    }
    
    void insert(string word) {
        Trie* node = this;
        for (auto c : word) {
            int i = c-'a';
            if (node->table[i] == nullptr) {
                node->table[i] = new Trie();
            }
            node = node->table[i];
        }
        node->isFinish = true;
    }
    
    bool search(string word) {
        Trie* node = this;
        for (auto c : word) {
            int i = c-'a';
            if (node->table[i] == nullptr)
                return false;
            node = node->table[i];
        }
        return node->isFinish;
    }
    
    bool startsWith(string prefix) {
        Trie* node = this;
        for (auto c : prefix) {
            int i = c-'a';
            if (node->table[i] == nullptr)
                return false;
            node = node->table[i];
        }
        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);
 */