단어 추가 및 검색 데이터 구조 설계

새 단어 추가를 지원하고 문자열이 이전에 추가된 문자열과 일치하는지 확인하는 데이터 구조를 설계합니다.
WordDictionary 클래스를 구현합니다.

WordDictionary() 객체를 초기화합니다.

void addWord(word) 데이터 구조에 word를 추가하고 나중에 일치시킬 수 있습니다.

bool search(word) 데이터 구조에 true와 일치하는 문자열이 있으면 word를 반환하고 그렇지 않으면 false를 반환합니다. word에는 점'.'이 포함될 수 있으며 점은 모든 문자와 일치할 수 있습니다.

예시:

입력
["단어 사전","addWord","addWord","addWord","검색","검색","검색","검색"]
[[],["나쁜"],["아빠"],["미친"],["패드"],["나쁜"],[".ad"],["b.."]]
산출
[널,널,널,널,거짓,참,참,참]

설명
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("나쁜");
wordDictionary.addWord("아빠");
wordDictionary.addWord("미친");
wordDictionary.search("패드");//거짓 반환
wordDictionary.search("나쁜");//참 반환
wordDictionary.search(".ad");//참 반환
wordDictionary.search("b..");//참 반환

제약:

1 <= word.length <= 25

word의

addWord는 영문 소문자로 구성되어 있습니다.

word in search는 '.' 또는 소문자 영문자로 구성됩니다.

3 쿼리에 대해 word에 최대 search개의 점이 있습니다.

최대 104 호출이 addWord 및 search 로 이루어집니다.

해결책:

class Node:
    def __init__(self, val=None, children=[], end=False):
        self.val = val
        self.children = children
        self.end = end

class WordDictionary:

    def __init__(self):
        self.root = Node(val=None, children=[])

    def addWord(self, word: str) -> None:
        n = len(word)
        curr = self.root
        for i, c in enumerate(word):
            found = False
            for node in curr.children:
                if node.val == c:
                    curr = node
                    found = True
                    break
            if not found:
                newcurr = Node(val=c, children=[])
                curr.children.append(newcurr)
                curr = newcurr
        curr.end = True

    def search(self, word: str) -> bool:
        n = len(word)
        paths = [(self.root, 0)]
        while len(paths) > 0:
            curr, i = paths.pop()
            if i == n and curr.end:
                return True
            if curr.children and i < n:
                for c in curr.children:
                    if word[i] == "." or c.val == word[i]:
                        paths.append((c, i + 1))
        return False

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