Leetcode 211. Design Add and Search Words Data Structure

Problem

Leetcode 211 - Design Add and Search Words Data Structure

Example:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

Approach

Similar to Leetcode 208, we can solve this using TrieNode, and for searching, we can use backtracking for each values in map.

Here is the Python code for the solution:

class TrieNode():

    def __init__(self):
        self.letterMap = {}
        self.endOfWord = False

class WordDictionary:

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

    def addWord(self, word: str) -> None:
        curr = self.root

        for ch in word:
            if ch not in curr.letterMap:
                curr.letterMap[ch] = TrieNode()
            curr = curr.letterMap[ch]
        curr.endOfWord = True

    def search(self, word: str) -> bool:
        
        def dfs(j, root):
            curr = root

            for i in range(j, len(word)):
                if word[i] == '.':
                    for key, val in curr.letterMap.items():
                        if dfs(i+1, val):
                            return True
                if word[i] not in curr.letterMap:
                    return False
                curr = curr.letterMap[word[i]]
            return curr.endOfWord
        
        return dfs(0, self.root)     

Time Complexity and Space Complexity

Time Complexity: $O(n)$ for each function call

Space Complexity: $O(t+n)$ where t is the total number of TrieNodes created in Trie