LeetCode Top Interview 150) Design Add and Search Words Data Structure

Question

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.

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 10^4 calls will be made to addWord and search.

class WordDictionary:

    def __init__(self):

    def addWord(self, word: str) -> None:

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

---

---

WordDictionary 클래스를 구현하는 문제입니다. addWord를 통해 단어를 저장할 수 있어야 하고, search를 통해 저장된 단어를 찾을 수 있어야 합니다. 이 때 search에서 word는 '.'이 포함될 수 있고 모든 단어가 될 수 있음을 의미합니다.

제가 생각한 코드는 다음과 같습니다.

class WordDictionary:

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

    def addWord(self, word: str) -> None:
        node = self.root
        
        for c in word:
            if c not in node:
                node[c] = {}
            node = node[c]
        
        node["*"] = {}

    def search(self, word: str) -> bool:
        n = len(word)

        def dfs(idx: int, node: dict) -> bool:
            if idx == n:
                return "*" in node
            
            if word[idx] == '.':
                for next_node in node:
                    if next_node != '*' and dfs(idx+1,node[next_node]):
                        return True
                        
            elif word[idx] in node:
                return dfs(idx+1,node[word[idx]])

            return False

        return dfs(0,self.root)

• self.root : 단어의 시작을 저장하는 딕셔너리입니다.
• addWord(word) : 입력받은 단어를 저장하는 함수입니다.
  • 시작 node를 self.root로 정의하고 단어의 문자를 순회합니다.
  • 순회하면서 해당 문자의 node로 이동합니다. 만약 없다면 해당 문자의 노드를 생성합니다.
  • 단어 입력이 끝나면 단어의 끝을 알리는 '*'문자를 추가합니다.
• search(word) : 입력받은 단어를 찾는 함수입니다.
  • 단어 길이 n을 정의합니다.
  • dfs(idx,node) : 현재 탐색중인 문자의 인덱스 idx와 탐색중인 노드 node를 가지는 깊이탐색 함수입니다.
    • idx가 길이와 같아졌다면(마지막 단어까지 탐색이 끝났다면) bool값을 리턴합니다. 이 때 단어의 끝을 확인해야 하므로 node내에 '*'의 유무를 반환합니다.
    • 현재 단어가 '.'이라면 현재 노드 내의 모든 문자를 탐색해야 합니다.
      ---- 다음 노드가 '*'이 아니고 다음 노드의 깊이 탐색 결과가 True라면 True를 반환합니다.
      ---- if문이 붙은 이유는 한 번이라도 True가 반환되면 되기 때문에 for문 전체를 순회하기 위함입니다.
    • 탐색하는 문자가 '.'이 아니고 노드 내에 있다면 다음 깊이의 dfs()함수를 호출합니다.
    • 문자에 없다면 False를 반환합니다.
• search함수의 반환값을 깊이탐색함수의 시작인 dfs(0,self.root)로 합니다.

---

'.' 처리에 대해 많이 어려게 느껴진 문제였습니다. '.'이 등장했을 때 단순히 반복문을 돌리려하면 여러 노드를 탐색할 수 없게 되므로 재귀 함수 형식으로 깊이 탐색을 했습니다.
그리고 '*'라던가 dfs()함수 자체가 조건으로 사용되는 방식을 적용하고 생각해내기까지 시행착오가 많았습니다.

조건문이 많아지면서 예외에 대해 고민하는게 어려웠던것 같습니다.