deepSWE.io

Design Add and Search Words Data Structure

TriesData Structures

Problem Statement

Design a data structure that supports adding new words and finding if a string matches any previously added string. Implement the WordDictionary class with the following methods:

WordDictionary() - Initializes the object
addWord(word) - Adds word to the data structure
search(word) - Returns true if there is any string that matches word, or false otherwise. word may contain dots '.' where dots can match any letter.

Example Structure

Words added: bad, dad, mad

Example searches:

search("pad") → false
search("bad") → true
search(".ad") → true
search("b..") → true

Key Features

• Support for '.' wildcard that can match any character
• Each word addition takes O(M) time, where M is word length
• Search complexity is O(M) for words without wildcards
• Search with wildcards requires exploring multiple paths
• Space complexity is O(N * M) where N is number of words

Algorithm Explanation

The Word Dictionary is implemented using a Trie (prefix tree) with support for wildcard pattern matching. Each node in the trie represents a character, with a special handling for the '.' wildcard character.

Key Operations

addWord: Insert the word into the trie by creating nodes for each character, marking the last node as end-of-word.
search: Navigate the trie, handling wildcards by exploring all possible child nodes when encountering a '.'.

Implementation Details

Node Structure: Each node contains a character and a map of child nodes.
Wildcard Handling: For '.' characters, recursively search all possible paths.
Search Algorithm: Uses DFS to explore potential matches when wildcards are present.
End Markers: Track word endings to distinguish complete words from prefixes.

Word Dictionary Search Visualization

Searching for pattern "b.d" in the dictionary

Start: Begin search for "b.d"

Starting search for word "b.d". Begin at root node.

Searching: "b.d"

B.D

Step 1 of 6

Current Node

End of Word

Regular Node

Code Example

class TrieNode:
    def __init__(self):
        self.children = {}  # character -> TrieNode
        self.is_end = False

class WordDictionary:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()
        
    def addWord(self, word: str) -> None:
        """
        Add a word into the data structure.
        Time complexity: O(M) where M is word length
        Space complexity: O(M)
        """
        curr = self.root
        for char in word:
            if char not in curr.children:
                curr.children[char] = TrieNode()
            curr = curr.children[char]
        curr.is_end = True

    def search(self, word: str) -> bool:
        """
        Returns true if there is a path from root to a leaf node 
        that matches the word pattern, allowing '.' to match any character.
        Time complexity: O(N * 26^M) where N is number of words and M is word length
        Space complexity: O(1) for iterative, O(M) for recursive stack
        """
        def dfs(node: TrieNode, i: int) -> bool:
            # Base case: reached end of word
            if i == len(word):
                return node.is_end
            
            char = word[i]
            if char == '.':
                # Try all possible characters
                for child in node.children.values():
                    if dfs(child, i + 1):
                        return True
                return False
            else:
                # Match specific character
                if char not in node.children:
                    return False
                return dfs(node.children[char], i + 1)
                
        return dfs(self.root, 0)