Leetcode 211. Design Add and Search Words Data Structure with Python

문제

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.

단어를 보관 및 검색 가능한 자료구조를 구성하시오
addWord(word: String) 메소드는 단어를 자료구조에 저장한다.
search(word: String) 메소드는 자료구조에서 단어를 찾아 결과를 boolean으로 리턴한다.
search시엔 문자로 .이 들어갈수 있는데, 이것은 이 자리에 어떤 문자가 와도 괜찮다는것을 의미한다.

예시

Input:

wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad");
wordDictionary.search("bad"); 
wordDictionary.search(".ad"); 
wordDictionary.search("b.."); 

Output:

False
True
True
True

제한

• 1 <= word.length <= 25
• 추가되는 단어는 영어 소문자로만 이루어져 있다.
• search시 최대 3개의 .만 존재한다.
• 최대 $10^4$개의 요청이 들어온다.

풀이법

trie를 이용하되 중간에 나오는 .만 특수하게 처리하도록 했다.

class Trie:
    def __init__(self):
        self.isEnd = False
        self.alphabet = {}
    def add(self, word: str):
        if len(word) == 0: 
            self.isEnd = True
            return
        char = ord(word[0])-ord('a')
        if char not in self.alphabet:
            self.alphabet[char] = Trie()
        self.alphabet[char].add(word[1:])
    def search(self, word:str):
        if len(word) == 0:
            return self.isEnd
        if word[0] == '.':
            for x in self.alphabet.values():
                if x.search(word[1:]):
                    return True
            return False
        char = ord(word[0])-ord('a')
        if char not in self.alphabet:
            return False
        else:
            return self.alphabet[char].search(word[1:])
                    

class WordDictionary:

    def __init__(self):
        self.head = Trie()

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

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