Implement Magic Dictionary

Explanation & Solution

Description

Design a data structure that is initialized with a list of different words. You are given a string and need to determine if you can change exactly one character in this string to match any word in the data structure.

Implement the MagicDictionary class:

MagicDictionary() — Initializes the object.
buildDict(dictionary) — Sets the data structure with an array of distinct strings dictionary.
search(searchWord) — Returns true if you can change exactly one character in searchWord to match a string in the dictionary, otherwise returns false.

Input:operations = ["MagicDictionary","buildDict","search","search","search","search"], operands = [[],[["hello","leetcode"]],["hello"],["hhllo"],["hell"],["leetcoded"]]

MagicDictionary

buildDict

Output:[null,null,false,true,false,false]

null

false

true

false

Explanation: The dictionary is built with ["hello", "leetcode"]. Searching "hello" returns false because changing one character cannot yield a different dictionary match. Searching "hhllo" returns true because changing 'h' to 'e' at index 1 yields "hello". Searching "hell" returns false (different length). Searching "leetcoded" returns false (different length).

Constraints

1 <= dictionary.length <= 100
1 <= dictionary[i].length <= 100
dictionary[i] consists of only lowercase English letters
All strings in dictionary are distinct
1 <= searchWord.length <= 100
searchWord consists of only lowercase English letters
At most 100 calls will be made to search

Approach

Trie pattern

1. Build a Trie from the Dictionary

Insert every word from the dictionary into a trie
Each node represents a character, and _end marks the end of a complete word

2. Search with Exactly One Change

For each search query, perform a depth-first search (DFS) through the trie
Track whether we have already made a character change using a boolean flag changed

3. DFS Traversal Logic

At each position in the search word, iterate over all children of the current trie node
If the child key matches the current character, continue without using the change
If the child key does not match and we have not yet made a change, try taking this branch with changed = true
If we have already made a change, skip non-matching children

4. Validate at Word End

When we reach the end of the search word, check two conditions:
The current trie node is marked as _end (a valid dictionary word)
Exactly one change was made (changed is true)
Both conditions must be met to return true

5. Process All Operations

Parse the operations array to create the dictionary, build it, and perform searches
Return the results array with null for constructor and buildDict calls

Key Insight

Using a trie with DFS allows us to explore all possible single-character substitutions efficiently. By branching at each mismatch and limiting to exactly one change, we avoid generating all possible modified strings explicitly.

Time

O(26 * L) per search where L is the word length (at most one branching point with 26 options)

Space

O(N * L) for the trie where N is the number of dictionary words

Solution Code

Count Prefix and Suffix Pairs

Lexicographical Numbers