[리트코드] 208. Implement Trie (Prefix Tree)

문제

https://leetcode.com/problems/implement-trie-prefix-tree/?envType=study-plan-v2&envId=top-interview-150

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

Constraints:

• 1 <= word.length, prefix.length <= 2000
• word and prefix consist only of lowercase English letters.
• At most 3 * 10**4 calls in total will be made to insert, search, and startsWith.

---

✔ 문제접근 #1 구현[통과] ⭕

Intuition
트라이 노드를 통하여 자료구조를 구현한다.

Algorithm
트라이노드는 현재 자신의 값이 끝값이지를 체크하는 is_end와 자신의 다음 문자에 해당하는 정보를 알려주는 childrend으로 구성된다. 영어 소문자로 이루어져 있기 때문에 children의 범위를 26으로 정해놓고 탐색한다.

class Trie:

    def __init__(self):
        self.is_end = False
        self.children = [None for _ in range(26)]

    def insert(self, word: str) -> None:
        t = self    
        for char in word:
            index = ord(char) - ord("a")
            
            if t.children[index] is None:
                t.children[index] = Trie()
                
            t = t.children[index]
        
        t.is_end = True
        

    def search(self, word: str) -> bool:
        t = self
        for char in word:
            index = ord(char) - ord("a")
            
            if t.children[index] is None:
                return False
            
            t = t.children[index]
            
        if t.is_end:
            return True
        else:
            return False
        

    def startsWith(self, prefix: str) -> bool:
        # 먼저 prefix까지 트라이를 타고 들어간다.
        # 만약 그아래에 더 트라이 노드가 존재한다면 prefix를 접두사로 갖는 단어가 최소 1개는 존재한다는 뜻이다.
        
        t = self
        for char in prefix:
            index = ord(char) - ord("a")
            if t.children[index] is None:
                return False
            
            t = t.children[index]
            
        
        # 만약 prefix자체가 있다면 True로 반환한다.
        if t.is_end:
            return True
        
        # 여기서 아래에 더 있는지 확인한다.
        for i in range(26):
            if t.children[i] is not None:
                return True          
        return False

 

Complexity Analysis

• 시간 복잡도 : O(M + N)
  • N < 2000, M < 3*10**4 
  • insert() 시간복잡도 O(N*M)
  • search() 시간복잡도 O(N)
  • startWith 시간복잡도 O(N)
  • 그러므로 전체시작복잡도 : O(N*M)

• 공간복잡도 : O(N)
  
  • 문자열의 길이에 따라 사용하는 children배열을 추가로 사용한다.

---

기타풀이 및 회고

해당 문제를 풀며 트라이 자료구조를 처음 공부해보게 되었다. 확실히 트라이 자료구조를 사용하지 않고 접두사 관계를 파악하려면 시간복잡도가 굉장히 높게 나올 것이라고 생각이 든다.

 

트라이 노드가 어떤 멤버변수를 가지고 있는지만 잘 생각한다면 메소드 구현은 크게 어렵지 않은 것 같다.

 

추가적으로 알파벳 소문자가 아닌경우도 잘 고려하여 children을 구성해야 될 것 같다.