문제

아래와 같은 동작을 구현하라.

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를 구현하는 방법에 대한 문제이지만, 그 전에 hashtable만 사용하여 아주 간단한게 풀어보았다.

• hashtable 방법
  insert() 함수에서 모든 prefix를 해시테이블에 값 1로 저장한다. 그리고 전체 word는 해시테이블에 2로 저장한다.
  그러면 해당 함수의 시간복잡도는 O(n)이다.(n문자열 길이).
  그러면 search 함수는 해시테이블에서 O(1) 만에 수행이된다(값이 2인 key가 존재하면 true). 그리고 startWith()함수는 key가 해시테이브레 존재하기만 하면 true를 리턴하면 된다.
  답은 맞아도 혹시 TLE 걸리지는 않을까 했는데 놀랍게도 runtime 24.74% 로 pass.

• trie 구현
  TBD

풀이 1 - hashtable

class Trie {
public:
    unordered_map<string, int> table;
    /*
    0: none
    1: prefix
    2: whole word
    */
    
    Trie() {
        
    }
    
    // O(n) word length: n
    void insert(string word) {
        string prefix = "";
        for (int i = 1; i < word.length(); i++) {
            prefix = word.substr(0, i);
            if (table.find(prefix) == table.end()) {
                table[prefix] = 1;
            }
        }    
        table[word] = 2;
    }
    
    // O(1)
    bool search(string word) {
        if (table.find(word) != table.end()) {
            if (table[word] == 2)
                return true;
        }
        return false;
    }
    
    // O(1)
    bool startsWith(string prefix) {
        if (table.find(prefix) != table.end())
             return true;
        return false;
    }
};

풀이 2 - Trie 구현

• trie_node 구조체나 클래스를 생성하고 이 노드를 계속해서 링크 시킨다. 흥미로운 점은 trie_node 구조체 멤버변수에 해당 문자를 저장할 변수를 추가할 필요가 없다는것. next 포인터배열의 인덱스가 바로 해당 문자이기 때문(해시테이블 key가 됨).
• 따라서 해당 노드가 초기화될때 next의 모든 값은 NULL로 초기화 시킨다. 그리고 search할때 해당 포인터가 NULL이라면 false가 된다.
• search()와 startwWith()의 차이점은 삽입할때 마지막 문자에 마킹(is_end)을 하고, trie자료구조내 word에 대한 마지막 문자에서 이 변수가 true인 문자열은 search에서 모든 문자열이 일치하므로 true가 된다.
• trie에서 insert와 find를 하는 for문의 동작이 매우 심플하면서도 좋다. 좋은 코드이니 잘 기억할것.

class trie_node {
public:
    trie_node *next[26];  
    bool is_end;

    trie_node() {
        memset(next, 0, sizeof(next));
        is_end = false;
    }
};

class Trie {
public:
    trie_node *root;
    Trie() {
        root = new trie_node;
    }
    
    void insert(string word) {
        trie_node *cur = root;
        for (int i = 0; i < word.size(); i++) {
            if (cur->next[word[i] - 'a'] == NULL) {
                cur->next[word[i] - 'a'] = new trie_node;
            }
            cur = cur->next[word[i] - 'a'];
        }
        cur->is_end = true;
    }
    
    bool search(string word) {
        trie_node *tgt = find(word);
        if (tgt && tgt->is_end == true)
            return true;
        return false;
    }
    
    bool startsWith(string prefix) {
        if (find(prefix))
            return true;
        return false;
        
    }
    trie_node *find(string s) {
        trie_node *cur = root;
        for (int i = 0; i < s.size() && cur; i++) {
            cur = cur->next[s[i] - 'a'];
        }
        return cur;
    }
};

풀이 230831

다시 풀음. 보다 캡슐화된 클래스.

class trie_node {
private:
    trie_node *next[26];
    int end;
public:
    trie_node() {
        memset(next, 0, sizeof(next));
        end = false;
    }
    trie_node *get_next(string w, int idx) {
        return next[w[idx] - 'a'];
    }
    void set_next(trie_node *t, string w, int idx) {
        next[w[idx] - 'a'] = t;
    }
    void set_end(void) {
        end = true;
    }
    bool is_end(void) {
        return end;
    }
};

class Trie {
public:
    trie_node *root;
    Trie() {
        root = new trie_node;
    }
    
    void insert(string word) {
        trie_node *cur = root;
        for (int i = 0; i < word.length(); i++) {
            if (cur->get_next(word, i) == NULL)
                cur->set_next(new trie_node, word, i);
            cur = cur->get_next(word, i);
        }
        cur->set_end();
    }
    
    bool search(string word) {
        trie_node *cur = root;
        for (int i = 0; i < word.length(); i++) {
            if (cur->get_next(word, i) == NULL)
                return false;
            cur = cur->get_next(word, i);
        }
        return cur->is_end();
    }
    
    bool startsWith(string prefix) {
        trie_node *cur = root;
        for (int i = 0; i < prefix.length(); i++) {
            if (cur->get_next(prefix, i) == NULL)
                return false;
            cur = cur->get_next(prefix, i);
        }
        return true;
    }
};