Skip to main content

211. Design Add and Search Words Data Structure

https://leetcode.com/problems/design-add-and-search-words-data-structure/

Python​

Trie Tree Mapper​

from functools import cache


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

    def addWord(self, word: str) -> None:
        cur = self.memory
        for letter in word:
            cur = cur.setdefault(letter, dict())
        cur['#'] = True

    def search(self, word: str) -> bool:
        def dfs(cur, i: int) -> bool:
            if i >= len(word):
                return '#' in cur if cur else False

            letter = word[i]

            if letter in cur:
                return dfs(cur[letter], i+1)

            if letter == '.':
                return any([dfs(child, i+1) for key, child in cur.items() if key != '#'])

            return False

        return dfs(self.memory, 0)