211.Design_Add_and_Search_Words_Data_Structure(Medium).md

211. Design Add and Search Words Data Structure (Medium)

Date and Time: Aug 13, 2024, 17:24 (EST)

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

Question:

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

• WordDictionary() Initializes the object.

• void addWord(word) Adds word to the data structure, it can be matched later.

• bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

Example 1:

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

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.

Walk-through:

Simlar to the previous question 208. Implement Trie (Prefix Tree), we need to create TrieNode() with self.children{}, self.endOfWord to store each character of word.

Everything is almost the same except we need to handle the case of "." in search(word) by calling dfs(i + 1, child), which i+1 is the next index of word, and child is one of the children in curr.children. Because we want to check if one of the child will work for ".ad" then it works. When word[i] is not "".", we just do the same thing as before to check.

We check if dfs(i+1, child): return True instead of if not dfs(i+1, child): return False, because we want to check if one of the children can work.

Python 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:
        curr = self.root
        for c in word:
            if c not in curr.children:
                curr.children[c] = TrieNode()
            curr = curr.children[c]
        curr.endOfWord = True

    def search(self, word: str) -> bool:
        curr = self.root
        def dfs(j, curr):
            for i in range(j, len(word)):
                if word[i] == '.':
                    for child in curr.children.values():
                        if dfs(i+1, child):
                            return True
                    return False
                else:
                    if word[i] not in curr.children:
                        return False
                    curr = curr.children[word[i]]
            return curr.endOfWord
        return dfs(0, curr)

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

Time Complexity: $O(n * m)$, where n is the number of words, m is the length of word.
Space Complexity: $O(n * m)$