Skip to main content

🟨 Design Add and Search Words Data Structure (#211)

🔗 Problem Link​

📋 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:

  • WordDictionary() Initializes the object.
  • void addWord(word) Adds word to the data structure.
  • 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.

💡 Examples​

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]

🔑 Key Insights & Approach​

Core Observation: Use Trie with DFS for wildcard searches. When encountering '.', try all possible children.

Why Trie + DFS?

  • addWord: O(m) where m = word length
  • search: O(m) for exact, O(26^m) worst case for wildcards
  • Handles wildcard efficiently

Approaches:

  1. Trie with DFS backtracking: Optimal for this problem

Pattern: "Trie with Wildcard Search" using DFS.

🐍 Solution: Python​

Approach: Trie with DFS​

Time Complexity: addWord O(m), search O(m) to O(26^m) | Space Complexity: O(N * M)

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

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

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

        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]

        node.is_word = True

    def search(self, word: str) -> bool:
        def dfs(index, node):
            if index == len(word):
                return node.is_word

            char = word[index]

            if char == '.':
                # Try all children
                for child in node.children.values():
                    if dfs(index + 1, child):
                        return True
                return False
            else:
                # Exact match
                if char not in node.children:
                    return False
                return dfs(index + 1, node.children[char])

        return dfs(0, self.root)

🔵 Solution: Golang​

Approach: Trie with DFS​

Time Complexity: addWord O(m), search O(m) to O(26^m) | Space Complexity: O(N * M)

type TrieNode struct {
    children map[rune]*TrieNode
    isWord   bool
}

type WordDictionary struct {
    root *TrieNode
}

func Constructor() WordDictionary {
    return WordDictionary{
        root: &TrieNode{
            children: make(map[rune]*TrieNode),
            isWord:   false,
        },
    }
}

func (this *WordDictionary) AddWord(word string) {
    node := this.root

    for _, char := range word {
        if _, exists := node.children[char]; !exists {
            node.children[char] = &TrieNode{
                children: make(map[rune]*TrieNode),
                isWord:   false,
            }
        }
        node = node.children[char]
    }

    node.isWord = true
}

func (this *WordDictionary) Search(word string) bool {
    return this.dfs(0, []rune(word), this.root)
}

func (this *WordDictionary) dfs(index int, word []rune, node *TrieNode) bool {
    if index == len(word) {
        return node.isWord
    }

    char := word[index]

    if char == '.' {
        // Try all children
        for _, child := range node.children {
            if this.dfs(index+1, word, child) {
                return true
            }
        }
        return false
    }

    // Exact match
    if child, exists := node.children[char]; exists {
        return this.dfs(index+1, word, child)
    }

    return false
}

📚 References​