Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Implement Magic Dictionary solution and explanation

MediumDepth-First SearchDesignHash TableString7 min read58.4% acceptanceUpdated 9 Apr 2026
Asked atBloombergGoogle
Practise Implement Magic Dictionary
14:27
花花酱 LeetCode 676. Implement Magic Dictionary - 刷题找工作 EP49Hua Hua · 14:27 · 3K viewsWatch on YouTube
8 more videos on this problem
  1. 花花酱 LeetCode 676. Implement Magic Dictionary - 刷题找工作 EP49Hua Hua · 14:27 · 3K views
  2. Mock Interview | LeetCode 676. Implement Magic Dictionary | PythonAH Tech · 11:43 · 3K views
  3. Leetcode-676. Implement Magic Dictionary | Trie SeriesRaman Bhari · 28:36 · 687 views
  4. 676. Implement Magic Dictionary (LeetCode)hakunamatasq · 6:09 · 614 views
  5. 676. Implement Magic Dictionary (Leetcode Medium)Programming Live with Larry · 12:28 · 554 views
  6. Leetcode 676. Implement Magic Dictionary (2 trie method)LetsCode · 20:15 · 354 views
  7. Implement Magic Dictionary, Medium, C++, LeetCodeH William Polenz · 24:09 · 155 views
  8. Implement Magic Dictionary | LeetCode #676 | Python Solution Explained Step-by-StepNidhi Chouhan · 20:19 · 38 views
  9. No Sound Leetcode 676: Implement Magic DictionaryExtremeProgrammer · 2:41 · 14 views

The problem

Design a data structure that is initialized with a list of different words. Provided a string, you should 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.
  • void buildDict(String[] dictionary) Sets the data structure with an array of distinct strings dictionary.
  • bool search(String searchWord) Returns true if you can change exactly one character in searchWord to match any string in the data structure, otherwise returns false.

Example 1:

Input
["MagicDictionary", "buildDict", "search", "search", "search", "search"]
[[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]
Output
[null, null, false, true, false, false]

Explanation
MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict(["hello", "leetcode"]);
magicDictionary.search("hello"); // return False
magicDictionary.search("hhllo"); // We can change the second 'h' to 'e' to match "hello" so we return True
magicDictionary.search("hell"); // return False
magicDictionary.search("leetcoded"); // return False

Constraints:

  • 1 <= dictionary.length <= 100
  • 1 <= dictionary[i].length <= 100
  • dictionary[i] consists of only lower-case English letters.
  • All the strings in dictionary are distinct.
  • 1 <= searchWord.length <= 100
  • searchWord consists of only lower-case English letters.
  • buildDict will be called only once before search.
  • At most 100 calls will be made to search.

Approach overview

Problem Overview: Design a data structure that stores a dictionary of words and supports a search operation that returns true only if you can modify exactly one character of the input word to match a stored word. Exact matches are not allowed; the match must differ by exactly one position.

Approach 1: Brute-force Comparison (Build: O(n*m), Search: O(n*m), Space: O(n*m))

Store all dictionary words in a list or set. During search, iterate through every stored word and compare it with the query character by character. Count how many positions differ. If exactly one character differs, return true. If the difference is zero or more than one, continue checking other words.

This approach relies purely on direct string comparison and works because the constraint "exactly one modification" can be verified by scanning both strings simultaneously. The downside is that every query potentially scans the entire dictionary. With n words of length m, the search cost becomes O(n*m). It’s simple and acceptable for small dictionaries but scales poorly.

Approach 2: Hash Map for Character Patterns (Build: O(n*m), Search: O(m), Space: O(n*m))

Precompute wildcard patterns for each dictionary word. For every position in a word, replace that character with a placeholder such as *. For example, the word hello generates patterns like *ello, h*llo, he*lo, hel*o, and hell*. Store these patterns in a hash table that maps each pattern to the number of words that produce it.

During search, generate the same patterns for the query word and check if any pattern exists in the hash map. A matching pattern means there is a dictionary word differing by one character at that position. Additional checks ensure the match isn't the same word when only one dictionary entry produces the pattern.

The key insight is transforming the "one character difference" rule into shared wildcard patterns. Each lookup becomes a constant-time hash operation. Since only m patterns are generated for a word of length m, search runs in O(m) time after preprocessing. This approach heavily leverages string manipulation and efficient hash table lookups.

Recommended for interviews: The hash map pattern approach is what most interviewers expect. It shows you can convert a character-difference constraint into a pattern indexing problem and optimize lookups using hashing. Explaining the brute-force comparison first demonstrates clear reasoning about the problem, while the optimized design highlights strong data structure skills commonly tested in design-style questions.

Approach 1: Brute-force Comparison

This approach iterates over each word in the dictionary and compares it to the search word by changing exactly one character at a time. If any change results in a match, the search returns true.

class MagicDictionary:
    def __init__(self):
        self.dictionary = []

    def buildDict(self, dictionary: List[str]) -> None:
        self.dictionary = dictionary

    def search(self, searchWord: str) -> bool:
        for word in self.dictionary:
            if len(word) != len(searchWord):
                continue
            count_diffs = sum(1 for x, y in zip(word, searchWord) if x != y)
            if count_diffs == 1:
                return True
        return False
import java.util.*;

class MagicDictionary {
    List<String> dictionary;

    public MagicDictionary() {
        dictionary = new ArrayList<>();
    }

    public void buildDict(String[] dict) {
        dictionary = Arrays.asList(dict);
    }

    public boolean search(String searchWord) {
        for (String word : dictionary) {
            if (word.length() != searchWord.length()) continue;
            int diff = 0;
            for (int i = 0; i < searchWord.length(); i++) {
                if (word.charAt(i) != searchWord.charAt(i)) {
                    diff++;
                }
                if (diff > 1) break;
            }
            if (diff == 1) return true;
        }
        return false;
    }
}
#include <vector>
#include <string>
using namespace std;

class MagicDictionary {
    vector<string> dictionary;
public:
    MagicDictionary() {}
    void buildDict(vector<string> dict) {
        dictionary = dict;
    }
    bool search(string searchWord) {
        for (const string& word : dictionary) {
            if (word.length() != searchWord.length()) continue;
            int diff = 0;
            for (int i = 0; i < searchWord.size(); ++i) {
                if (word[i] != searchWord[i]) ++diff;
                if (diff > 1) break;
            }
            if (diff == 1) return true;
        }
        return false;
    }
};
class MagicDictionary {
    constructor() {
        this.dictionary = [];
    }

    buildDict(dict) {
        this.dictionary = dict;
    }

    search(searchWord) {
        for (let word of this.dictionary) {
            if (word.length !== searchWord.length) continue;
            let diff = 0;
            for (let i = 0; i < searchWord.length; i++) {
                if (word[i] !== searchWord[i]) diff++;
                if (diff > 1) break;
            }
            if (diff === 1) return true;
        }
        return false;
    }
}
#include <stdbool.h>
#include <string.h>

typedef struct {
    char **dictionary;
    int size;
} MagicDictionary;

MagicDictionary* magicDictionaryCreate() {
    MagicDictionary* obj = (MagicDictionary*) malloc(sizeof(MagicDictionary));
    obj->dictionary = NULL;
    obj->size = 0;
    return obj;
}

void magicDictionaryBuildDict(MagicDictionary* obj, char ** dictionary, int size) {
    obj->dictionary = dictionary;
    obj->size = size;
}

bool magicDictionarySearch(MagicDictionary* obj, const char * searchWord) {
    for (int i = 0; i < obj->size; i++) {
        if (strlen(obj->dictionary[i]) != strlen(searchWord)) continue;
        int diff = 0;
        for (int j = 0; j < strlen(searchWord); j++) {
            if (searchWord[j] != obj->dictionary[i][j]) diff++;
            if (diff > 1) break;
        }
        if (diff == 1) return true;
    }
    return false;
}

void magicDictionaryFree(MagicDictionary* obj) {
    free(obj);
}
using System;
using System.Collections.Generic;

public class MagicDictionary
{
    private List<string> dictionary;
    
    public MagicDictionary() {
        dictionary = new List<string>();
    }

    public void BuildDict(string[] dict) {
        dictionary.AddRange(dict);
    }

    public bool Search(string searchWord) {
        foreach (var word in dictionary) {
            if (word.Length != searchWord.Length) continue;
            int diff = 0;
            for (int i = 0; i < searchWord.Length; i++) {
                if (word[i] != searchWord[i]) diff++;
                if (diff > 1) break;
            }
            if (diff == 1) return true;
        }
        return false;
    }
}

In Python, we create a class utilizing a list for storing words. The search function checks for differences by zipping through characters of the search word and dictionary words.

Complexity

Time Complexity: O(n * m), where n is the number of words and m is the average word length. Space Complexity: O(1).

Try this approach in the editor

Approach 2: Hash Map for Character Patterns

We optimize search by utilizing hash maps to store patterns for similar length words with one character removed at each position. During the search check, modified search word patterns are created and checked against stored patterns.

from collections import defaultdict
from typing import List

class MagicDictionary:
    def __init__(self):
        self.patterns = defaultdict(set)

    def buildDict(self, dictionary: List[str]) -> None:
        for word in dictionary:
            for i in range(len(word)):
                pattern = word[:i] + '*' + word[i+1:]
                self.patterns[pattern].add(word)

    def search(self, searchWord: str) -> bool:
        for i in range(len(searchWord)):
            pattern = searchWord[:i] + '*' + searchWord[i+1:]
            if pattern in self.patterns:
                candidates = self.patterns[pattern]
                if len(candidates) > 1 or searchWord not in candidates:
                    return True
        return False
import java.util.*;

class MagicDictionary {
    Map<String, Set<String>> patterns = new HashMap<>();

    public MagicDictionary() {}

    public void buildDict(String[] dict) {
        for (String word : dict) {
            for (int i = 0; i < word.length(); ++i) {
                String pattern = word.substring(0, i) + '*' + word.substring(i + 1);
                patterns.computeIfAbsent(pattern, k -> new HashSet<>()).add(word);
            }
        }
    }

    public boolean search(String searchWord) {
        for (int i = 0; i < searchWord.length(); ++i) {
            String pattern = searchWord.substring(0, i) + '*' + searchWord.substring(i + 1);
            if (patterns.containsKey(pattern) && (!patterns.get(pattern).contains(searchWord) || patterns.get(pattern).size() > 1)) {
                return true;
            }
        }
        return false;
    }
}
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <string>
using namespace std;

class MagicDictionary {
    unordered_map<string, unordered_set<string>> patterns;
public:
    MagicDictionary() {}
    void buildDict(vector<string> dict) {
        for (const string& word : dict) {
            for (int i = 0; i < word.length(); ++i) {
                string pattern = word.substr(0, i) + '*' + word.substr(i + 1);
                patterns[pattern].insert(word);
            }
        }
    }
    bool search(string searchWord) {
        for (int i = 0; i < searchWord.length(); ++i) {
            string pattern = searchWord.substr(0, i) + '*' + searchWord.substr(i + 1);
            if (patterns.count(pattern) > 0) {
                auto candidates = patterns[pattern];
                if (candidates.size() > 1 || candidates.count(searchWord) == 0) {
                    return true;
                }
            }
        }
        return false;
    }
};
class MagicDictionary {
    constructor() {
        this.patterns = new Map();
    }

    buildDict(dict) {
        for (const word of dict) {
            for (let i = 0; i < word.length; i++) {
                let pattern = word.slice(0, i) + '*' + word.slice(i + 1);
                if (!this.patterns.has(pattern)) this.patterns.set(pattern, new Set());
                this.patterns.get(pattern).add(word);
            }
        }
    }

    search(searchWord) {
        for (let i = 0; i < searchWord.length; i++) {
            let pattern = searchWord.slice(0, i) + '*' + searchWord.slice(i + 1);
            if (this.patterns.has(pattern)) {
                let candidates = this.patterns.get(pattern);
                if (candidates.size > 1 || !candidates.has(searchWord)) {
                    return true;
                }
            }
        }
        return false;
    }
}
#include <stdbool.h>
#include <string.h>
#include <stdio.h>

typedef struct {
    char **patterns;
    int *counts;
    int size;
} MagicDictionary;

MagicDictionary* magicDictionaryCreate() {
    MagicDictionary* obj = (MagicDictionary*) malloc(sizeof(MagicDictionary));
    obj->patterns = (char **) malloc(sizeof(char*) * 100);
    obj->counts = (int *) malloc(sizeof(int) * 100);
    obj->size = 0;
    return obj;
}

void magicDictionaryBuildDict(MagicDictionary* obj, char ** dictionary, int size) {
    obj->size = size;
    int index = 0;
    for (int i = 0; i < size; i++) {
        int len = strlen(dictionary[i]);
        for (int j = 0; j < len; j++) {
            char *pattern = (char *) malloc(sizeof(char) * len);
            sprintf(pattern, "%.*s%c%s", j, dictionary[i], '*', &dictionary[i][j + 1]);
            obj->patterns[index] = pattern;
            obj->counts[index++] = 1;
        }
    }
    obj->size = index;
}

bool magicDictionarySearch(MagicDictionary* obj, const char * searchWord) {
    int len = strlen(searchWord);
    for (int i = 0; i < len; i++) {
        char pattern[101];
        snprintf(pattern, sizeof(pattern), "%.*s%c%s", i, searchWord, '*', &searchWord[i + 1]);
        for (int j = 0; j < obj->size; j++) {
            if (strcmp(obj->patterns[j], pattern) == 0) {
                return true;
            }
        }
    }
    return false;
}

void magicDictionaryFree(MagicDictionary* obj) {
    for (int i = 0; i < obj->size; i++) {
        free(obj->patterns[i]);
    }
    free(obj->patterns);
    free(obj->counts);
    free(obj);
}
using System;
using System.Collections.Generic;

public class MagicDictionary {
    private Dictionary<string, HashSet<string>> patterns;
    
    public MagicDictionary() {
        patterns = new Dictionary<string, HashSet<string>>();
    }

    public void BuildDict(string[] dict) {
        foreach (string word in dict) {
            for (int i = 0; i < word.Length; i++) {
                string pattern = word.Substring(0, i) + '*' + word.Substring(i + 1);
                if (!patterns.ContainsKey(pattern)) {
                    patterns[pattern] = new HashSet<string>();
                }
                patterns[pattern].Add(word);
            }
        }
    }

    public bool Search(string searchWord) {
        for (int i = 0; i < searchWord.Length; i++) {
            string pattern = searchWord.Substring(0, i) + '*' + searchWord.Substring(i + 1);
            if (patterns.ContainsKey(pattern)) {
                var candidates = patterns[pattern];
                if (candidates.Count > 1 || !candidates.Contains(searchWord)) {
                    return true;
                }
            }
        }
        return false;
    }
}

Using Python's defaultdict, we map patterns generated from dictionary words. The search checks transformed searchWord patterns in this dictionary to verify candidates efficiently, saving runtime and effort.

Complexity

Time Complexity: O(n + m), where n represents the number of words and m represents the search length. Space Complexity: O(n * m).

Try this approach in the editor

Approach 3: Trie + DFS

We can use a trie to store all the words in the dictionary. For each word we search, we use depth-first search. Specifically, we start from the root of the trie. For the current letter we are traversing, we first check whether there is a child node that is the same as it. If there is, we continue to traverse downwards. Otherwise, we need to check whether there are remaining modification times. If not, it means that it cannot be matched, so we return false. If there are remaining modification times, we can try to modify the current letter and continue to traverse downwards. If the child node corresponding to the modified letter exists, it means that it can be matched, otherwise it means that it cannot be matched, so we return false. If we traverse to the end of the word and the number of modifications is exactly 1, it means that it can be matched, so we return true.

The time complexity is O(n times l + q times l times |\Sigma|), and the space complexity is O(n times l), where n and l are the number of words in the dictionary and the average length of the words, respectively, and q is the number of words searched. In addition, |\Sigma| represents the size of the character set. Here, the character set is lowercase English letters, so |\Sigma|=26.

class Trie {
    private children: Trie[] = Array(26).fill(null);
    private isEnd: boolean = false;

    constructor() {}

    insert(w: string): void {
        let node: Trie = this;
        for (const c of w) {
            const i: number = c.charCodeAt(0) - 'a'.charCodeAt(0);
            if (!node.children[i]) {
                node.children[i] = new Trie();
            }
            node = node.children[i];
        }
        node.isEnd = true;
    }

    search(w: string): boolean {
        const dfs = (i: number, node: Trie, diff: number): boolean => {
            if (i >= w.length) {
                return diff === 1 && node.isEnd;
            }
            const j: number = w.charCodeAt(i) - 'a'.charCodeAt(0);
            if (node.children[j] && dfs(i + 1, node.children[j], diff)) {
                return true;
            }
            if (diff === 0) {
                for (let k = 0; k < 26; k++) {
                    if (k !== j && node.children[k] && dfs(i + 1, node.children[k], 1)) {
                        return true;
                    }
                }
            }
            return false;
        };
        return dfs(0, this, 0);
    }
}

class MagicDictionary {
    private trie: Trie;

    constructor() {
        this.trie = new Trie();
    }

    buildDict(dictionary: string[]): void {
        for (const w of dictionary) {
            this.trie.insert(w);
        }
    }

    search(searchWord: string): boolean {
        return this.trie.search(searchWord);
    }
}

/**
 * Your MagicDictionary object will be instantiated and called as such:
 * var obj = new MagicDictionary()
 * obj.buildDict(dictionary)
 * var param_2 = obj.search(searchWord)
 */
type Trie struct {
	children [26]*Trie
	isEnd    bool
}

func NewTrie() *Trie {
	return &Trie{}
}

func (t *Trie) Insert(w string) {
	node := t
	for _, c := range w {
		i := c - 'a'
		if node.children[i] == nil {
			node.children[i] = NewTrie()
		}
		node = node.children[i]
	}
	node.isEnd = true
}

func (t *Trie) Search(w string) bool {
	var dfs func(int, *Trie, int) bool
	dfs = func(i int, node *Trie, diff int) bool {
		if i >= len(w) {
			return diff == 1 && node.isEnd
		}
		j := int(w[i] - 'a')
		if node.children[j] != nil && dfs(i+1, node.children[j], diff) {
			return true
		}
		if diff == 0 {
			for k := 0; k < 26; k++ {
				if k != j && node.children[k] != nil && dfs(i+1, node.children[k], 1) {
					return true
				}
			}
		}
		return false
	}
	return dfs(0, t, 0)
}

type MagicDictionary struct {
	trie *Trie
}

func Constructor() MagicDictionary {
	return MagicDictionary{trie: NewTrie()}
}

func (md *MagicDictionary) BuildDict(dictionary []string) {
	for _, w := range dictionary {
		md.trie.Insert(w)
	}
}

func (md *MagicDictionary) Search(searchWord string) bool {
	return md.trie.Search(searchWord)
}

/**
 * Your MagicDictionary object will be instantiated and called as such:
 * obj := Constructor();
 * obj.BuildDict(dictionary);
 * param_2 := obj.Search(searchWord);
 */
struct Trie {
    children: [Option<Box<Trie>>; 26],
    is_end: bool,
}

impl Trie {
    fn new() -> Self {
        Trie {
            children: Default::default(),
            is_end: false,
        }
    }

    fn insert(&mut self, w: &str) {
        let mut node = self;
        for c in w.chars() {
            let i = (c as usize) - ('a' as usize);
            if node.children[i].is_none() {
                node.children[i] = Some(Box::new(Trie::new()));
            }
            node = node.children[i].as_mut().unwrap();
        }
        node.is_end = true;
    }

    fn search(&self, w: &str) -> bool {
        self.dfs(w, 0, 0)
    }

    fn dfs(&self, w: &str, i: usize, diff: usize) -> bool {
        if i == w.len() {
            return diff == 1 && self.is_end;
        }

        let j = (w.chars().nth(i).unwrap() as usize) - ('a' as usize);

        if let Some(child) = &self.children[j] {
            if child.dfs(w, i + 1, diff) {
                return true;
            }
        }

        if diff == 0 {
            for k in 0..26 {
                if k != j {
                    if let Some(child) = &self.children[k] {
                        if child.dfs(w, i + 1, 1) {
                            return true;
                        }
                    }
                }
            }
        }
        false
    }
}

struct MagicDictionary {
    trie: Trie,
}

impl MagicDictionary {
    fn new() -> Self {
        MagicDictionary {
            trie: Trie::new(),
        }
    }

    fn build_dict(&mut self, dictionary: Vec<String>) {
        for w in dictionary {
            self.trie.insert(&w);
        }
    }

    fn search(&self, search_word: String) -> bool {
        self.trie.search(&search_word)
    }
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Brute-force Comparison

Time Complexity: O(n * m), where n is the number of words and m is the average word length. Space Complexity: O(1).

Hash Map for Character Patterns

Time Complexity: O(n + m), where n represents the number of words and m represents the search length. Space Complexity: O(n * m).

Trie + DFS–

Complexity analysis

ApproachTimeSpaceWhen to Use
Brute-force ComparisonBuild: O(n*m), Search: O(n*m)O(n*m)Small dictionaries or quick prototype where implementation simplicity matters more than speed
Hash Map for Character PatternsBuild: O(n*m), Search: O(m)O(n*m)General case and interview settings where fast query time is required

Frequently asked questions

Is Implement Magic Dictionary easy or hard?

Implement Magic Dictionary is rated Medium because the brute-force idea is straightforward but the optimal solution requires recognizing the wildcard pattern trick. Understanding how to convert a one-character difference rule into a hash lookup is the key insight.

Implement Magic Dictionary Python/Java solution

Python and Java implementations typically build a HashMap or dictionary where keys are wildcard patterns like 'h*llo'. During search, the algorithm generates patterns for the query word and checks the map for matches while ensuring exactly one character difference.

How to solve Implement Magic Dictionary in O(n)?

The practical optimal solution is O(n*m) preprocessing and O(m) search using a hash map of wildcard patterns. Each word produces m patterns by replacing one character with '*'. During search, matching patterns quickly identify words that differ by exactly one character.

What is the best approach for Implement Magic Dictionary?

The hash map wildcard pattern approach is the most efficient and commonly expected solution. Each dictionary word generates patterns by replacing one character with '*', which are stored in a hash table. During search, the query word generates the same patterns and checks for matches in O(m) time after O(n*m) preprocessing.

Is Implement Magic Dictionary asked at Google/Amazon/Meta?

Design-style dictionary problems and string mutation checks appear frequently in interviews at companies like Google, Amazon, and Meta. Variants often test hash table usage, string manipulation, and data structure design concepts similar to Magic Dictionary.

What data structure is used in Implement Magic Dictionary?

The most common solution uses a hash table that maps wildcard string patterns to counts or lists of dictionary words. Alternatives may use tries or direct string comparison, but the hash map pattern technique provides the best balance of simplicity and performance.

What is the time complexity of Implement Magic Dictionary?

Using the optimized hash map pattern approach, building the dictionary takes O(n*m) time where n is the number of words and m is the word length. Each search operation runs in O(m) because only m wildcard patterns are generated and checked in a hash table.

Comments

Next problem · similarImplement Trie (Prefix Tree)Medium
Now write it yourselfClose this page and solve Implement Magic Dictionary in the editor, without looking.
Practise Implement Magic Dictionary