[python3] 208. Implement Trie (Prefix Tree)

풀이 일자: 23.03.17

난이도: [Medium]

분류: [Hash Table, String, Trie]

문제 내용

Trie라는 class를 구현해보는 문제로 삽입과 탐색, 부분탐색 함수의 내용을 구현하면 된다.

 

문제 해결 흐름

1. 구현해야 하는 내용은 분명하므로 어떤 자료구조를 이용하여 이를 구현할건지를 생각해보면 될 것 같다.

→ 크게 3가지를 떠올렸는데 

 

1)  배열에 넣는 것 만으로도 배열의 인덱스가 이진트리의 역할을 하도록 하는 방법

→ 하나씩 insert 되기 때문에 insert하면서 정렬을 하는 건 시간낭비일 것 같아서 탐색도 linear하게 삽입도 linear하게 처리해보았다.

class Trie:

    def __init__(self):
        self.trie = list();

    def insert(self, word: str) -> None:
        self.trie.append(word);
        
    def search(self, word: str) -> bool:
        for w in self.trie:
            if word == w:
                return True;
        return False; 

    def startsWith(self, prefix: str) -> bool:
        for w in self.trie:
            if w.find(prefix, 0, len(prefix)) != -1:   #startswith라는 내장함수 사용 가능
                return True;
        return False;


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

=> 너무나 Naive한 방법으로 정렬도 안하고 단순히 찾기만 해서 문제이나 배열만 사용하여 공간복잡도 측면에서는 유리

Time Complexity:  insert ( O(1) )  search ( O(N) ), startsWith (O(NM) )

insert는 append하기 때문에 1의 시간복잡도

search는 N개의 insert된 트리노드를 탐색해야하기 때문에 N의 시간복잡도

startsWith는 N개의 insert된 트리노드를 탐색하면서 크기(M)에 맞게 잘라서 비교하니까 NM의 시간복잡도

 

Space Complexity: O(N)

N개의 insert된 노드를 저장하기에 공간복잡도는 N이 될 것이다.

 

 

 

2) 탐색을 조금 더 효율적으로 해보자.. 자료를 넣을 때마다 정렬하고 탐색에 좋은 자료구조가 있었는데

→  Top Priority Queue 혹은 Min Heap이라고 하는 자료구조를 생각해보자.

 

class Trie:
    def __init__(self):
        self.hq = list();

    def insert(self, word: str) -> None:
        heappush(self.hq, word);

    def search(self, word: str) -> bool:
        tmp = list(self.hq);
        while(len(tmp) != 0):
            if tmp[0] == word:
                return True;
            elif tmp[0] > word:
                return False;
            else:
                heappop(tmp);
        return False;
    
    def startsWith(self, prefix: str) -> bool:
        pLen = len(prefix);
        tmp = list(self.hq);
        while(len(tmp) != 0):
            if pLen > len(tmp[0]):
                heappop(tmp);
            else:
                if tmp[0][:pLen] == prefix:
                    return True;
                elif tmp[0][:pLen] > prefix:
                    return False;
                else:
                    heappop(tmp);
        return False;

=> 넣으면서 정렬을 하는 Min heap을 사용했으나 결과적으로는 탐색하는 시간은 일반 배열을 사용하는 것과 큰 차이가 없기 때문에 엄청난 시간의 Runtime을 보여준다.

 

Time Complexity:  insert ( O(LogN) )  search ( O(N) ), startsWith (O(NM) )

insert는 minHeap에 insert하는 시간의 LogN의 시간복잡도

search는 N개의 insert된 트리노드를 탐색해야하기 때문에 N의 시간복잡도

startsWith는 N개의 insert된 트리노드를 탐색하면서 글자길이(M)만큼 탐색

 

Space Complexity: O(N)

N개의 insert된 노드를 저장하기에 공간복잡도는 N이 될 것이다.

 

 

 

3) Class명이 Trie니까 순순히 TreeNode Class를 이용해서 Trie를 만들어버리자.

→  Trie를 만드는 건 확정이고 현재 탐색에서 시간이 많이 걸리는거니까 이진탐색트리로 만드는 것이 좋겠다.

class TreeNode:
    def __init__(self, val = None, left = None, right = None):
        self.left = left;
        self.right = right;
        self.val = val;

class Trie:
    def __init__(self):
        self.root = None;

    def insert(self, word: str) -> None:
        if self.root == None:
            self.root = TreeNode(word);
        else:
            curr = self.root;
            while (curr):
                if curr.val > word:
                    if curr.left == None:
                        curr.left = TreeNode(word);
                        break;
                    curr = curr.left;
                elif curr.val < word:
                    if curr.right == None:
                        curr.right = TreeNode(word);
                        break;
                    curr = curr.right;
                else:
                    break;

    def search(self, word: str) -> bool:
        curr = self.root;
        while (curr):
            if curr.val > word:
                curr = curr.left;
            elif curr.val < word:
                curr = curr.right;
            else:
                return True;
        return False;
        

    def startsWith(self, prefix: str) -> bool:
        pLen = len(prefix);
        curr = self.root;
        while (curr):
            cLen = len(curr.val)
            if pLen > cLen:
                if curr.val > prefix[:cLen]:
                    curr = curr.left;
                else:
                    curr = curr.right
            else:
                if curr.val[:pLen] == prefix:
                    return True
                elif curr.val[:pLen] > prefix:
                    curr = curr.left;
                else:
                    curr = curr.right;
        return False;

=> TreeNode를 통한 탐색이 이루어지기 때문에 탐색또한 LogN의 시간복잡도를 보여 공간이나 시간적인 측면에서 모두 유리한 방법이었다.

 

Time Complexity:  insert ( O(LogN) )  search ( O(LogN) ), startsWith (O(MLogN) )

insert는 minHeap에 insert하는 시간의 LogN의 시간복잡도

search는 N개의 insert된 트리노드를 탐색하기에 LogN의 시간복잡도

startsWith는 N개의 insert된 트리노드를 탐색하면서 크기(M)에 맞게 잘라서 비교하니까 MLogN의 시간복잡도

 

Space Complexity: O(N)

N개의 insert된 노드를 저장하기에 공간복잡도는 N정도 될 것이다.  배열을 트리로 생각했을 때와 인스턴스들을 연결하여 트리를 만들었을 때와의 공간복잡도 차이를 생각해봤을 땐 배열보다는 공간복잡도가 높을 것이다.

 

 

다른 해결 방식

1. 공식 풀이에서는 TreeNode class를 따로 생성하지 않고 단어를 한 문자 단위로 쪼개서 List로 관리하고 있다.

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

Implement Trie (Prefix Tree) - LeetCode

 

문제 링크

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

Implement Trie (Prefix Tree) - LeetCode