[LeetCode] 211 | Design Add and Search Words Data Structure

---

문제 링크: https://leetcode.com/problems/design-add-and-search-words-data-structure/

---

문제

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.

---

조건

• 1 <= word.length <= 500
• word in addWord consists lower-case English letters.
• word in search consist of  '.' or lower-case English letters.
• At most 50000 calls will be made to addWord and search.

---

내 풀이

보자마자 Maximum XOR of Two Numbers in an Array에서 사용한 Trie구조를 사용해야겠다는 생각이 들었다.

addWord 함수는 Trie에 단어를 집어넣는다.

search함수를 구현할때는 '.'에 신경써야 한다.

'.'이 들어올 때는 현재 node에 있는 모든 경우의 수를 고려하도록 recursive하게 짜면 된다. (조건에서 최대 50000 calls라고했으니 recursive라는 것을 이미 눈치챘을 수도 있다.)

---

코드

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

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

    def search(self, word: str) -> bool:
        def withDot(node, word):
            if not word:
                return '$' in node
            elif word[0] == '.':
                for n in node:
                    if n is not '$':
                        if withDot(node[n], word[1:]):
                            return True
                return False
            else:
                if word[0] not in node:
                    return False
                else:
                    return withDot(node[word[0]], word[1:])
            
        return withDot(self.trie, word)
                


# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)