#211

Design Add and Search Words Data Structure

medium· Triesruns: 0

Design a data structure that supports adding new words and searching with single-character wildcards. Implement addWord(word) and search(word). search returns true if the word matches any added word, where '.' acts as a wildcard for any single letter.

wpm 0acc 100%time 0:000 / 928

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class WordDictionary:
    def __init__(self):
        self.root = TrieNode()

    def addWord(self, word: str) -> None:
        curr = self.root
        for c in word:
            if c not in curr.children:
                curr.children[c] = TrieNode()
            curr = curr.children[c]
        curr.is_end = True

    def search(self, word: str) -> bool:
        def dfs(i: int, node: TrieNode) -> bool:
            if i == len(word):
                return node.is_end
            c = word[i]
            if c == ".":
                for child in node.children.values():
                    if dfs(i + 1, child):
                        return True
                return False
            if c not in node.children:
                return False
            return dfs(i + 1, node.children[c])

        return dfs(0, self.root)

click the box to focus · tab inserts 4 spaces · backspace to correct · esc to pause

desktop only

codedrill is a typing game and needs a real keyboard. open this on a laptop or desktop to practice.

you can still browse problems and sections from your phone.