📕문제

[Leetcode] 211. Design Add and Search Words Data Structure

문제 설명

단어 등록과 단어 검색을 할 수 있는 자료구조를 만드는 문제다.
생성자와 자료구조를 word를 등록하는addWord(word) 함수, 자료구조에서 word를 검색하는 searchWord(word)함수를 완성해야 한다.
검색 함수에서 word는 점(.)을 최대 2개까지 포함할 수 있으며 점은 모든 문자를 대체할 수 있다.
예를들어 bad라는 단어가 자료구조에 존재할 때 ..d를 검색하면 True를 반환한다.

---

📝풀이

처음 문제를 접했을 때 단순히 리스트를 만들고 첫글자로 후보군을 줄인 후 ==연산을 통해 단어를 비교하려고 했다.
하지만 word에 모든 문자를 대체할 수 있는 .이 존재하기 때문에 일일이 비교해야 했고, 이 방식은 큰 시간복잡도를 가진다는 것을 알고 그만뒀다.
그러다 Trie라는 자료구조를 발견했다.

Trie

Trie는 문자열을 저장하고 효율적으로 탐색하기 위한 Tree형태의 자료구조다.

위 그림은 POT, PAST, PASS, PART를 저장한 Trie다.
예를들어 PART를 검색한다고 하면 P, A, R, T 순서로 검색하게 된다.
이 때 P, A, R 노드를 거치며 탐색 후보군을 줄이게 되고 이로인해 단어를 일일이 비교하는 것 보다 시간복잡도 측면에서 더 효율적이다.

먼저 Trie를 구현해보았다.

Node

class Node(object):
    def __init__(self, key, data=None):
        self.key = key
        self.data = data
        self.children = {}

노드는 다음과 같은 정보들을 가진다.

• 값으로 입력될 문자인 key.
• 문자열이 끝날 때 해당 문자열을 저장할 data. 해당 값으로 문자열이 종료됨을 알 수 있다.
• 자식노드를 저장할 children.

Trie
생성자

    def __init__(self):
        self.head = Node(None)

• Trie가 생성될 때 key값을 가지지 않는 head 노드를 생성한다.

addword

    def addWord(self, word: str) -> None:
        curr = self.head
        for char in word:
            if char not in curr.children:
                curr.children[char] = Node(char)
            curr = curr.children[char]
        curr.data = word

• curr값을 head로 설정해 head 노드부터 탐색 시작한다.
• 문자열의 문자가 curr의 children에 존재하지 않는다면 해당 문자를 key값으로 갖는 노드를 생성 후 children에 추가하며 하나씩 검사한다.
• 문자열이 끝나면 마지막 노드의 data값에 해당 문자열을 저장한다.

search

    def search(self, word: str) -> bool:
        curr = self.head
        for char in word:
            if char in curr.children:
                curr = curr.children[char]
            else:
                return False
        if curr.data:
            return True
        else:
            return False

• curr값을 head로 설정해 head 노드부터 탐색 시작한다.
• 문자열의 문자를 하나씩 돌면서 children에 존재하는지 검사한다. 중간에 존재하지 않는다면 False를 반환.
• 탐색을 마친 후 마지막 노드에 data값이 존재한다면 True, 그렇지 않으면 False를 반환한다.
  data값이 필요한 이유: 사전에 FARM이라는 단어가 존재한다고 가정할 때 FAR를 검색한 결과는 False이어야 하기 때문.

해당 Trie에 모든 문자를 대체할 수 있는 .이라는 문제의 조건을 추가하기 위해선 search 함수만 수정하면 된다.

수정된 search()

    def search(self, word: str, curr=None) -> bool:
        if not curr:
            curr = self.head
        for i in range(len(word)):
            char = word[i]
            if char == '.':
                for c in curr.children:
                    if self.search(word[i+1:], curr.children[c]):
                        return True
                return False
            elif char in curr.children:
                curr = curr.children[char]
            else:
                return False
        if curr.data:
            return True
        else:
            return False

• 탐색 중 .를 만난다면 해당 노드의 모든 children값에 대해 serch 함수를 재귀 실행한다. 이때 탐색중인 노드의 위치를 저장하기 위해 매개변수 curr를 만들었다.

통과는 했지만 좀 느리다.

leetcode의 코드 샘플을 둘러보다 딕셔너리를 활용한 코드를 발견해 가져와봤다.
딕셔너리를 쓸 생각은 해봤지만 .의 존재때문에 첫글자를 key로 사용할 수 없을 것 같아 포기했었는데 이 코드에는 문자열의 길이를 key로 사용했다.

생성자

    def __init__(self):
        self.trie = defaultdict(set)
        self.visited = dict()

• trie와 visited 두개의 딕셔너리를 가진다. trie는 문자열을 저장하기 위한 딕셔너리, visited는 이전에 검색한 문자열에 대한 검색결과를 저장해 똑같은 문자열을 검색했을 때 검색 과정을 생략해준다.

addWord

    def addWord(self, word: str) -> None:
        self.trie[len(word)].add(word)

• trie에 문자열의 길이를 key값, 문자열을 value값으로 추가한다.

search

    def search(self, word: str) -> bool:
        N = len(word)
        key = (word, len(self.trie[N]))
        if key in self.visited:
            return self.visited[key]

        for candidate in self.trie[N]:
            i, j = 0, 0
            is_found = True
            # both length are supposed to be equal
            while i < len(candidate) and j < len(word):
                if candidate[i] != word[j] and word[j] != ".":
                    is_found = False
                    break
                i += 1
                j += 1
            if is_found:
                self.visited[key] = True
                return True
        self.visited[key] = False
        return False

• 문자열이 visited에 존재한다면, 즉 이전게 검색한 기록이 있다면 저장했던 결과값을 반환한다.
• trie내에서 word의 길이가 key 값인 문자열들이 후보군이 된다.
• 후보군과 word를 하나씩 비교하며 다른 문자가 존재하면 탐색을 종료하고 다른 후보군과의 비교를 시작한다.
• 검색을 마치면 visited를 업데이트하고 결과를 반환한다.

처음에 생각한 하나하나 비교하는 방식과 유사했지만 문자열의 첫글자를 key로 가져야한다는 생각에 사로잡혀 떠올리지 못한방법이다.
추가로 이전에 검색했던 문자열을 저장해 중복 탐색을 방지해 좀 더 효율적이다.
하지만 같은 길이인 문자열이 많은 경우 효율성이 떨어지는 방법인 것 같다.