211. Design Add and Search Words Data Structure

MediumLeetCode

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

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.

How to solve the problem

• Set (Time Limit Exceeded)
• Trie (Recommended)

# Approach 1: Set
class WordDictionary:

    def __init__(self):
        self.word_set = set()

    def addWord(self, word: str) -> None:
        self.word_set.add(word)

    def search(self, word: str) -> bool:
        for w in self.word_set:
            if len(w) != len(word):
                continue
            for a, b in zip(w, word):
                if b != "." and a != b:
                    break
            else:
                # for loop not break means all characters matched
                return True
        return False

# Approach 2: Trie
class TrieNode:
    def __init__(self):
        self.children = {}  # Mapping from character to TrieNode
        self.is_end = False  # Indicates if a word ends here

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

    def addWord(self, word: str) -> None:
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_end = True  # Mark the end of a word

    def search(self, word: str) -> bool:
        def dfs(node, i):
            if i == len(word):
                # If we've reached the end of the word, check if it's a valid word
                return node.is_end
            c = word[i]
            if c == ".":
                # If the current character is '.', try all possible child nodes
                for child in node.children.values():
                    if dfs(child, i + 1):
                        return True
                return False
            else:
                # If the current character exists, continue the search
                if c not in node.children:
                    return False
                return dfs(node.children[c], i + 1)

        return dfs(self.root, 0)

Complexity

• Approach 1 (Set): Time complexity: O(N * L), Space complexity: O(N * L)
• Approach 2 (Trie): Time complexity: O(L^2), Space complexity: O(N * L)