211. 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

Constraints:

• 1 <= word.length <= 25
• word in addWord consists of lowercase English letters.
• word in search consist of ‘.’ or lowercase English letters.
• There will be at most 2 dots in word for search queries.
• At most 10^4 calls will be made to addWord and search.

Approach

Solution

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


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

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

    # Leverage Recursion
    def search(self, word: str) -> bool:
        def dfs(j, root):
            cur = root
            for i in range(j, len(word)):
                c = word[i]

                if c == ".":
                    for child in cur.children.values():
                        if dfs(i + 1, child):
                            return True
                    return False
                else:
                    if c not in cur.children:
                        return False
                    cur = cur.children[c]
            return cur.endOfWord

        return dfs(0, self.root)


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

Explanation