LeetCode [ 211 | Python ] Design Add And Search Words Data Structure

문제

https://leetcode.com/problems/design-add-and-search-words-data-structure/description/?envType=study-plan-v2&envId=top-interview-150

이전 문제와 비슷하지만, 와일드 카드 문자 .를 포함해 검색을 수행해야 하는 Trie 문제.

풀이

위에서 언급했던 이전 문제와 차이는 search 함수에 있다.
이 search 함수는 와일드 카드를 포함하는데 그저 접두어, 접미어를 찾아야 하는 것이 아니라 해당 와일드 카드 문자를 포함한 길이의 단어를 찾아야 하는 점이 까다롭게 느껴졌다.

우선 와일드 카드 문자를 처리할 때 다음의 방법을 고려했다.

1. 저장시에 모든 노드의 자손 노드에 .를 저장한다. 해당 와일드카드에 대한 자손모두 갱신되어야 한다. 또한 이것이 가능하다해도 과다한 메모리를 사용할 것 같다고 생각했다.
2. 검색시에 .를 처리한다.
   1. .를 만나면 건너뛴다 건너 뛴다면 다음 노드에서 판단할 기준이 없어진다.
   2. .를 만나면 모든 자손에 대해 검색한다.

이후에 위의 과정에 따라서 와일드 카드에 대해 모든 자손에 대해 검색하기로 결정했다.

정답

실행 시간 : 2070ms 메모리 : 107.7MB

1. 초기화, addWord는 이전 문제의 insert 함수와 같게 구현했다.

2. search 와일드 카드를 포함한 단어의 저장 여부를 반환하는 함수.

   1. 재귀 탐색을 위한 내부 함수 search를 구현한다.
      1. 현재 탐색하는 node와 word의 철자를 추출하기 위한 주소값 idx 를 매개변수로 입력 받는다.
      2. 변수 c에 탐색하려는 철자 word[idx]를 저장한다.
      3. 현재 철자 c가 와일드카드 문자 .인지 확인한다.
         1. .에 해당하는 문자라면 현재 노드의 모든 노드에 대해 재귀호출한다.
         2. 재귀호출한 함수의 반환값이 True라면 True를 반환한다.
         3. .에 해당하는 문자가 아니라면 다음을 판단한다.
            1. 현재 노드의 자손에 c가 포함된다면 해당 노드를 입력으로 하여 재귀 호출한다.
            2. 현재 노드의 자손에 c가 포함되지 않는다면 False를 반환한다.
      4. 주소값 idx가 주어진 단어의 길이를 벗어나면 해당 노드의 단어 끝 여부 isEndOfWord를 반환한다.
   2. 내부함수 search를 호출한다.
      ```python
      class WordDictionary(object): root = {}

   def init(self): self.root[‘isEndOfWord’] = False self.root[‘children’] = {}

   def addWord(self, word): cur = self.root

    for c in word:
        if not c in cur['children']:
            cur['children'][c] = {'children' : {}, 'isEndOfWord' : False}
        cur = cur['children'][c]
   
    cur['isEndOfWord'] = True
       
    return
   

   def search(self, word): def search(node, idx = 0): if idx >= len(word): return node[‘isEndOfWord’]

        c = word[idx]
   
        if c == '.':
            for k in node['children'].keys():
                if search(node['children'][k], idx + 1):
                    return True
   
        else:
            if not c in node['children']:
                return False
            return search(node['children'][c], idx + 1)
           
       
    return search(self.root) ```   ### 시도 2   시도 1 과 같은 방법으로 진행하되, 입력시 `isEndOfWord` 를 `True`로 변경하는 과정에서 그 단어의 길이도 함께 저장하는 식으로 변경했다.   하지만 길이를 비교하는 것과는 별개로 로직이 복잡한 것은 변함이 없고 그만큼 내부 실행 과정이 파악하기 어려워져 탐색 방식을 하나로 통일하기로 했다.   ```python   ...  def search(self, word):
   
    def search(node, idx):
   
        cur = node
   
        for c in word[idx:]:
            if c == '.':
                for child in cur['children'].keys():
                    if search(cur['children'][child], idx + 1):
                        return True
   
            elif not c in cur['children']:
                return False
            else:
                cur = cur['children'][c]
   
        if cur['isEndOfWord'] :
            if cur['size'] == len(word):
                return True
            elif cur['size'] < len(word) and len(cur['children']) > 0:
                return True
        return False
   
    return search(self.root, 0) ```     ### 시도 1   다른 노드에 대해서는 반복문으로 처리하고, 와일드 카드를 만나면 모든 자손 키 값을 입력으로 하는 재귀를 호출해 처리하고자 했다.   로직이 복잡해지고 현재까지 찾았던 문자와 입력받은 `word`와의 길이를 비교할 수 없어서 더이상 진행할 수 없었다. ```python   ...  def search(self, word):
    def search(node, idx):
        cur = node
   
        for c in word[idx:]:
            if c == '.':
                for child in cur['children'].keys():
                    return search(cur['children'][child], idx + 1)
            elif not c in cur['children']:
                return False
            else:
                cur = cur['children'][c]
   
        return cur['isEndOfWord']
   
    return search(self.root, 0) ``` ## 생각 & 정리 시도 1에서 한참 고민을하며 size를 추가하는 선택을 했는데, Trie를 사용한 문자 자동 완성 기능을 만들때는 어떤 로직을 가질까 고민하는 시간을 가지게 되었다.  
   

이미 가지고 있는 단어 데이터베이스 내에서 조건에 부합하는 문자를 표현하고자해도, 그 단어들을 직접 출력해야될텐데.. 라는 고민이 들었기 때문이다.

그렇다면 새로운 리스트, 또는 배열을 만들어 매 탐색할 때 마다 단어에 철자를 추가해 만들지 않을까 ? 라는 생각으로 당착했고 이를 wanted에서 제공해준 샘플 코드에서 확인할 수 있었다.

샘플 코드

public List<String> autocomplete(String prefix) {
    Node currentNode = this.root

    for (char c: prefix.toCharArray()) {
        Node child = currentNode.children.get(c);

        if (child == null) return new ArrayList<>();

        currentNode = child;
    }		
    return searchStartWith(currentNode, new StringBuilder(prefix)));
}



public List<String> searchStartWith(Node node, StringBuilder prefix){
    List<String> results = new ArrayList<>();

    if(node.isEndOfWord) {
        results.add(prefix.toString());
    }

    for (Map.Entry<Character, Node> entry: node.children.entrySet()){
        prefix.append(entry.getKey()); 

        results.addAll(searchStartWith(entry.getValue(), prefix));

        prefix.deleteCharAt(prefix.length() - 1);
    }

    return results;
}

또한 반복문으로 Trie를 구현하는 것에 대해 다시 한번 생각해보게 되었다.
이전 문제를 풀면서 들었던 고민을 먼 고민처럼 말했지만, 그런 것과는 무색하게 바로 와일드카드를 처리하게 되면서 재귀로 표현하게 되었다.

와일드 카드에 대해서 반복문으로 처리할 방법이 있을지에 대한 생각도 해봐야겠다.