[Leetcode]Implement Trie (Prefix Tree)

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

LeetCode - The World's Leading Online Programming Learning Platform

 

문제 분석

Trie 자료 구조를 구현하는 문제입니다. insert, search, startsWith 함수를 구현하면 됩니다.

 

처음 시도한 답안

class Trie:

    def __init__(self):
        self.trie = {}
        
    def insert(self, word: str) -> None:
        trie = self.trie

        for w in word:
            if w not in trie:
                trie[w] = {}
            trie = trie[w]
        trie['*'] = True

    def search(self, word: str) -> bool:
        trie = self.trie

        for w in word:
            if w not in trie:
                return False
            trie = trie[w]

        if '*' in trie:
            return True

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

        for p in prefix:
            if p not in trie:
                return False
            trie = trie[p]

        return True

"""
{
    'a': {
        'p': {
            'p' : {
                'l' : {
                    'e': {
                        '*': True
                    }
                }
                '*': 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)

접근 방법

1. Trie 자료 구조를 딕셔너리를 활용해 구현합니다.
2. __init__ 시에는 딕셔너리를 초기화 합니다.
3. insert 시에는 input의 word를 char 단위로 반복합니다.
   1. char가 Trie에 존재하지 않으면 키를 char로 하는 딕셔너리를 생성합니다.
   2. trie를 한 depth 깊이 이동합니다.
   3. 단어가 끝나는 시점에 * 키와 True라는 값을 추가해줌으로써 해당 단어가 완성이 되었다는 것을 표시합니다.
4. search 시에는 input의 word를 char 단위로 반복합니다.
   1. 반복하면서 char가 Trie에 존재하지 않으면 단어가 없는 것이므로 False를 리턴합니다.
   2. char가 있다면 다음 depth Trie로 이동합니다.
   3. 반복이 종료된 경우에 * 키를 만나게 되면 해당하는 단어가 Trie에 존재하는 것이므로 True를 리턴합니다.
5. startsWith 시에는 Input의 word를 char 단위로 반복합니다.
   1. 반복하면서 char가 Trie에 존재하지 않으면 단어가 없는 것이므로 False를 리턴합니다.
   2. char가 있다면 다음 depth Trie로 이동합니다.
   3. 반복이 종료된 경우라면 해당 단어로 시작하는 단어가 Trie에 존재하는 것이므로 True를 리턴합니다.

Trie 자료 구조를 이전에 구현해본적이 있었는데 기억이 나지 않아서 파이썬의 어떤 자료구조를 사용해야할지를 몰랐던 문제입니다. 널리 쓰이는 딕셔너리를 활용해 구현하기로 결정했습니다. (링크드 리스트, 알파벳 갯수 만큼의 배열 등 다른 방법도 존재합니다)

 

코드 주석에서의 예시를 보는 편이 가장 이해가 쉬울 것 같습니다. 또한, 존재하는 단어의 경우에는 마지막에 * 값을 통해 단어가 존재한다는 표시를 해두었습니다.