[LeetCode] 208. Implement Trie (Prefix Tree)

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

Implement Trie (Prefix Tree) - LeetCode

Implement Trie

 

 

Trie 를 만드는 문제다.

정석적인 트리를 이용한 trie가 아닌 문제조건이 좀더 간단하고 자유로워 map을 이용해 풀었다.

들어오는 word의 모든 prefix를 map에 (prefix, 1)로 저장하고 word는 (word, 2)로 저장했다.

아래는 전체 코드이다.

 

class Trie {
public:
    map<string,int> m;
    Trie() {
        this->m.clear();
    }
    
    void insert(string word) {
        for (int i=0; i<word.size(); i++) {
            string sub = word.substr(0,i);
            if (this->m.find(sub)==this->m.end() || this->m[sub]!=2) this->m[sub] = 1;
        }
        this->m[word] = 2;
    }
    
    bool search(string word) {
        return this->m.find(word)!=this->m.end() && this->m.find(word)->second==2;
    }
    
    bool startsWith(string prefix) {
        return this->m.find(prefix)!=this->m.end();
    }
};

 

정석적인 방법은

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

Implement Trie (Prefix Tree) - LeetCode

 

위 사이트에 Java 코드로 올라와있다.

tree를 이용해 앞 글자부터 차례대로 가지를 달아주는 것이다.

 

아래는 참고하여 c++코드로 구현해본 것이다.

반드시 확인해보자!

class Trie {
public:
    Trie() {
        for (int i=0; i<26;i++) children[i] = NULL;
        val = 0;
    }
    
    void insert(string word) {
        Trie* cur = this;
        for (int i=0; i<word.size(); i++) {
            if (cur->children[word[i]-'a']==NULL) cur->children[word[i]-'a'] = new Trie();
            cur = cur->children[word[i]-'a'];
        }
        cur->val = 1;
        return;
    }
    
    bool search(string word) {
        Trie* cur = this;
        for (int i=0; i<word.size(); i++) {
            if (cur->children[word[i]-'a']==NULL) return false;
            cur = cur->children[word[i]-'a'];
        }
        return cur->val==1;
    }
    
    bool startsWith(string prefix) {
        Trie* cur = this;
        for (int i=0; i<prefix.size(); i++) {
            if (cur->children[prefix[i]-'a']==NULL) return false;
            cur = cur->children[prefix[i]-'a'];
        }
        return true;
    }
private:
    int val;
    Trie* children[26];
};