4 분 소요

Trie

문제

문제 링크

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

  • WordDictionary() Initializes the object.
  • void addWord(word) Adds word to the data structure, it can be matched later.
  • bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

Example:

Input ["WordDictionary","addWord","addWord","addWord","search","search","search","search"] [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]] Output [null,null,null,null,false,true,true,true]

Explanation WordDictionary wordDictionary = new WordDictionary(); wordDictionary.addWord(“bad”); wordDictionary.addWord(“dad”); wordDictionary.addWord(“mad”); wordDictionary.search(“pad”); // return False wordDictionary.search(“bad”); // return True wordDictionary.search(“.ad”); // return True wordDictionary.search(“b..”); // return True

Constraints:

  • 1 <= word.length <= 25
  • word in addWord consists of lowercase English letters.
  • word in search consist of '.' or lowercase English letters.
  • There will be at most 2 dots in word for search queries.
  • At most 104 calls will be made to addWord and search.

스스로 고민

접근법

  • 어떤 단어가 입력되면 그 단어와 일치한다면 true를 반환해주면된다.
  • word 라는 단어가 있다면 .ord 이런 식으로 입력해도 true를 반환해야한다
  • . 은 최대 2개 까지 조합될 수 있다.

의사코드

  • 처음에 그냥 별 생각 없이 트라이 노드를 사용하고 처음 노드를 만들기 시작할 때 부터 .을 섞어서 만들 생각을 했다.
  • 애초에 app 이라는 단어가 있다면 a 의 차일드 노드로 . 랑 p가 함께 들어가도록 만들면 괜찮을 거라고 생각했다.

  • 근데 생각해보니 차일드 노드를 변경할 때 두 번 각각 적용해서 차일드 노드를 새로 열어야 되기 때문에 처음부터 . 를 포함해서 저장하는 방법보단 그냥 찾는 방법으로 문제를 해결 하는 게 낫다고 생각했다.

  • 트라이 자료구조 + 스택으로 문제를 해결해봤다.
  • 단어를 추가하는건 기존 트라이 자료구조 구현과 동일하게 한다.
  • search 를 구현할 때 리스트안에 튜플로 데이터를 담아준다..
  • stack (리스트안에 데이터가) 비어 있을 때까지 while 문이 실행된다.
  • 튜플안에는 루트 노드와 인덱스 0이 들어가게 만든다
  • 단어 길이를 처음부터 검사하기 때문에 초기 인덱스는 0 그리고 마지막 인덱스가 되었을 경우 해당 단어가 끝났는지 확인을 해주면된다.
  • 그 이외에는 글자가 . 로 실행하는지 확인하고 . 로 시작할 경우 노드의 벨류값 -> 트라이 노드들을 전부 스택에 넣어준다 그리고 index 는 +1
  • 예를 들어 처음에 “apple” 과 “bad” 두 개를 넣었다면 현재 a 와 b 이렇게 두 개만 있으 거다.
  • 인덱스가 돌아가면서 자식노드에 키 값이 일치하면 스택에 쌓이고 조건 이 만족하면 인덱스와 노드들이 업데이트 된다
  • 만족하지 않을 경우 아무것도 하지 않게되고 stack이 비어있게 되면 False를 반환해서 일치하는 단어가 담겨있지 않음을 알려준다.

    구현 코드

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

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

    def addWord(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_of_word = True

    def search(self, word: str) -> bool:
        stack = [(self.root, 0)]
        
        while stack:
            node, index = stack.pop()
            
            if index == len(word):
                if node.is_end_of_word:
                    return True
                continue

            char = word[index]

            if char == '.':
                for child in node.children.values():
                    stack.append((child, index + 1))
            elif char in node.children:
                stack.append((node.children[char], index + 1))

        return False

시간 복잡도와 공간 복잡도

시간 복잡도:

  1. addWord 함수: Trie에 단어를 추가하는 데 O(M) 시간이 걸린다. 여기서 M은 추가하는 단어의 길이다.
  2. search 함수: Trie에서 문자열을 검색하는 데 O(M) 시간이 걸린다. 여기서 M은 검색하는 문자열의 길이다. 이 함수는 와일드카드 문자 ‘.’을 처리하기 위해 모든 가능한 경로를 탐색하지만, 이 경로의 수는 Trie의 크기와 무관하게 일정하므로 O(M) 시간이 소요된다.

공간 복잡도:

  1. addWord 함수: 단어를 Trie에 추가하는 데 필요한 공간은 추가하는 단어의 길이에 비례한다. 따라서 모든 추가된 단어의 길이의 합에 비례하는 공간이 소요된다.
  2. Trie 자체의 공간 복잡도는 Trie에 저장된 단어의 총 길이에 비례한다. 최악의 경우 모든 단어가 서로 다른 문자로 이루어져 있다고 가정하면, Trie 자체의 공간 복잡도는 O(N) 다. 여기서 N은 Trie에 저장된 총 문자 수다.

회고 과정

보통 두 번 풀면 대충 어떤 느낌인지 이해가 되면서 응용이 가능했는데 이번에는 뭔가 응용하기가 많이 어려웠다.
아직 제대로 이해한 것 같지 않아서 해당 문제를 다른 사람들이 어떤 방식으로 풀었는지 알아보기로 했다.

다른 사람 코드를 보고 그 기준으로 어떤 부분을 개선 할 수 있는지 최종 회고

class WordDictionary:

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

    def addWord(self, word: str) -> None:
        node = self.trie 
        for letter in word:
            if letter not in node:
                node[letter] = {}
            node = node[letter]
        node["$"] = True

    def search(self, word: str) -> bool:
        def explore(word, node):
            if not word:
                return "$" in node
            
            letter = word[0]
            if letter == '.':
                for child in node:
                    if child != '$' and explore(word[1:], node[child]):
                        return True
            else:
                if letter not in node:
                    return False
                    
                return explore(word[1:], node[letter])
            
            return False

        return explore(word, self.trie)
  • 트라이 노드 구현 없이 재귀호출과 슬라이싱으로 문제를 해결한 케이스다
  • . 가 포함될 경우 [1:] 이렇게 해당 . 를 제거하고 다시 재귀 호출울 해서 문제를 푼 케이스다.
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

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

    def addWord(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_of_word = True

    def search_helper(self, word: str, node: TrieNode) -> bool:
        for i, char in enumerate(word):
            if char == '.':
                for child in node.children.values():
                    if self.search_helper(word[i+1:], child):
                        return True
                return False
            elif char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

    def search(self, word: str) -> bool:
        return self.search_helper(word, self.root)
  • 트라이노드도 사용하고 재귀호출도 사용하고 내가 푼 방법과 밑에 방법을 짬뽕한 느낌이다.
  • word 로 받는 데이터를 다시 딕셔너리 형태로 만든 다음 슬라이싱과 재귀호출로 계속 불러내는데 개인적으로 좀 복잡한거 같고 가독성이 좋지 않은거 같아서 이해만 하고 넘어가는 게 좋다고 생각했다.

댓글남기기

참고