LeetCode 208. Implement Trie (Prefix Tree)

파이썬 알고리즘 인터뷰 56번(리트코드 208) Implement Trie (Prefix Tree)
https://leetcode.com/problems/implement-trie-prefix-tree/

나의 풀이

class Trie:

    def __init__(self):
        self.set = set()

    def insert(self, word: str) -> None:
        self.set.add(word)

    def search(self, word: str) -> bool:
        return word in self.set

    def startsWith(self, prefix: str) -> bool:
        for word in self.set:
            if prefix == word[:len(prefix)]:
                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)

다른 풀이1

class TrieNode:
    def __init__(self):
        self.is_end = False
        self.children = collections.defaultdict(TrieNode)

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            node = node.children[char]
        node.is_end = True

    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end

    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

# 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)

다른 풀이2

class TrieNode:
    def __init__(self):
        self.is_end = False  # 단어의 끝 여부
        self.children = {}   # 자식 노드를 저장할 dict

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()  # 필요할 때만 노드 생성
            node = node.children[char]
        node.is_end = True  # 단어의 끝 표시

    def findNode(self, prefix: str):
        """주어진 prefix가 있는 노드를 찾음"""
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

    def search(self, word: str) -> bool:
        """완전한 단어 검색"""
        node = self.findNode(word)
        return node is not None and node.is_end  # 존재하고 단어 끝이면 True

    def startsWith(self, prefix: str) -> bool:
        """접두사(prefix) 확인"""
        return self.findNode(prefix) is not None

• defaultdict이 편리하지만 불필요한 노드를 많이 만들 수 있어서 이를 사용하지 않은 풀이.
• findNode를 이용하여 search, startsWith의 중복된 코드를 줄임.

다른 풀이3

class Trie:

    def __init__(self):
        self.root = {}

    def insert(self, word: str) -> None:
        cur = self.root

        for letter in word:
            if letter not in cur:
                cur[letter] = {}
            cur = cur[letter]
        
        cur['*'] = ''

    def search(self, word: str) -> bool:
        cur = self.root
        for letter in word:
            if letter not in cur:
                return False
            cur = cur[letter]

        return '*' in cur        

    def startsWith(self, prefix: str) -> bool:

        cur = self.root
        for letter in prefix:
            if letter not in cur:
                return False
            cur = cur[letter]
        return True
        

# 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)

배운 점

• 트라이(trie)가 트리(tree) 구조인 것은 알았으나, 자식의 수가 2개가 아니라 알파벳 수 만큼 가능해서 어떻게 트리로 구현할 지 막막하였음. dict을 이용하는구나.
• defaultdict에 내가 만든 class를 기본 값으로 넣을 수 있구나.
• 리트코드에서 풀이에 주어진 템플릿 위에 class를 추가할 수 있구나.