NUHMAN.com

🧩 Problem Statement

Design a data structure that supports adding new words and searching for a string, where . can represent any letter.

Implement the WordDictionary class:

go

type WordDictionary struct {
    // implement
}

func Constructor() WordDictionary
func (this *WordDictionary) AddWord(word string)
func (this *WordDictionary) Search(word string) bool

• AddWord(word) adds word to the data structure.
• Search(word) returns true if word matches any previously added word. A word could contain the dot character '.' to represent any one letter.

🧪 Example

go

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]

🧠 Approach

We use a Trie (Prefix Tree) to store words efficiently.

To handle . in search:

• Traverse all child nodes recursively when . is encountered.
• For regular characters, just follow the matching child.

✅ Go Implementation

go

package main

import "fmt"

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

type WordDictionary struct {
    root *TrieNode
}

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

func (this *WordDictionary) AddWord(word string) {
    node := this.root
    for _, ch := range word {
        if _, ok := node.children[ch]; !ok {
            node.children[ch] = &TrieNode{children: make(map[rune]*TrieNode)}
        }
        node = node.children[ch]
    }
    node.isEnd = true
}

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

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

    ch := word[index]
    if ch == '.' {
        for _, child := range node.children {
            if dfs(child, word, index+1) {
                return true
            }
        }
        return false
    }

    if child, ok := node.children[ch]; ok {
        return dfs(child, word, index+1)
    }

    return false
}

📦 Example Usage

go

func main() {
    dict := Constructor()
    dict.AddWord("bad")
    dict.AddWord("dad")
    dict.AddWord("mad")

    fmt.Println(dict.Search("pad")) // false
    fmt.Println(dict.Search("bad")) // true
    fmt.Println(dict.Search(".ad")) // true
    fmt.Println(dict.Search("b..")) // true
}

⏱️ Complexity

• AddWord
• Time: O(n), where n is length of the word.
• Search
• Worst-case Time: O(26^d), where d is the length of the word and all characters are ..
• Space: O(N * L) where N is number of words and L is average word length.

🧠 Key Concepts

• Trie traversal
• Recursive DFS for wildcard search
• Dot . as wildcard character

Let me know if you want a Breadth-First Search (BFS) variation or a version with memory optimization tips!