Problem statement

Design a dictionary that answers: can you change exactly one character of a given word so that it becomes a word in the dictionary? Write the class MagicDictionary:

• MagicDictionary() creates the object.
• void buildDict(String[] dictionary) fills it with a list of distinct words.
• boolean search(String searchWord) returns true if changing exactly one character of searchWord (to a different letter) turns it into a dictionary word, false otherwise.

A word that is already in the dictionary does not count by itself — one character must change.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every void method.

Example 1

Input: ["MagicDictionary","buildDict","search","search","search","search"]
[[],[["hello","leetcode"]],["hello"],["hhllo"],["hell"],["leetcoded"]]
Output: [null,null,false,true,false,false]
Explanation: "hello" itself needs zero changes, so it is false. "hhllo" becomes "hello" by changing its second letter. Lengths must match, so "hell" and "leetcoded" can never work.

Example 2

Input: ["MagicDictionary","buildDict","search","search","search"]
[[],[["hello","hallo","a"]],["hello"],["b"],["hxllx"]]
Output: [null,null,true,true,false]
Explanation: "hello" is in the dictionary, but changing its 'e' to 'a' gives "hallo", which is too — so it is true. "b" → "a" works; "hxllx" differs from "hello" in two places.

Constraints

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

Hints for Implement Magic Dictionary

1. Hint 1

   A dictionary word can only be reached if it has the same length as the search word.

2. Hint 2

   For a candidate of the same length, count the positions where the two words differ.

3. Hint 3

   The answer is true exactly when some same-length word differs in exactly one position; stop counting a candidate as soon as it reaches two differences.

How to solve Implement Magic Dictionary

Changing exactly one character of searchWord gives word w precisely when w has the same length and differs from searchWord in exactly one position. With at most 100 words of length at most 100, checking each same-length word directly is fast; grouping the words by length skips the others.

Approach

1. buildDict: group the words by length.
2. search(s): for each word w of length |s|, count positions i with w[i] != s[i], stopping at 2.
3. Return true as soon as some word has exactly one difference; false if none does.

Why it works

Changing one character to a different letter produces a word at Hamming distance exactly 1 from the original, and every word at distance 1 can be produced that way. So the question is whether the dictionary holds a word at Hamming distance 1 — which the scan checks word by word.

Complexity

• Time — O(N · L) per search for N words of length L; O(N · L) to build
• Space — O(N · L)

Pitfalls

• A search word that is itself in the dictionary is not automatically true — it needs a different word one change away.
• Words of a different length can never match; checking them wastes time and risks index errors.
• For far more searches, precompute every "generalised neighbour" (h*llo, one * per position) with its count — the standard O(L²) per search alternative.

Reference solution

Python

from typing import List

class MagicDictionary:

    def __init__(self):
        self.by_len = {}

    def buildDict(self, dictionary: List[str]) -> None:
        for w in dictionary:
            self.by_len.setdefault(len(w), []).append(w)

    def search(self, searchWord: str) -> bool:
        for w in self.by_len.get(len(searchWord), []):
            diff = 0
            for a, b in zip(w, searchWord):
                if a != b:
                    diff += 1
                    if diff > 1:
                        break
            if diff == 1:
                return True
        return False

Java

class MagicDictionary {
    private Map<Integer, List<String>> byLen = new HashMap<>();

    public MagicDictionary() {
    }

    public void buildDict(String[] dictionary) {
        for (String w : dictionary) byLen.computeIfAbsent(w.length(), k -> new ArrayList<>()).add(w);
    }

    public boolean search(String searchWord) {
        for (String w : byLen.getOrDefault(searchWord.length(), Collections.emptyList())) {
            int diff = 0;
            for (int k = 0; k < w.length() && diff < 2; k++) if (w.charAt(k) != searchWord.charAt(k)) diff++;
            if (diff == 1) return true;
        }
        return false;
    }
}

C++

class MagicDictionary {
    unordered_map<int, vector<string>> byLen;
public:
    MagicDictionary() {}

    void buildDict(vector<string> dictionary) {
        for (auto& w : dictionary) byLen[w.size()].push_back(w);
    }

    bool search(string searchWord) {
        auto it = byLen.find(searchWord.size());
        if (it == byLen.end()) return false;
        for (auto& w : it->second) {
            int diff = 0;
            for (size_t k = 0; k < w.size() && diff < 2; k++) if (w[k] != searchWord[k]) diff++;
            if (diff == 1) return true;
        }
        return false;
    }
};

JavaScript

var MagicDictionary = function() {
    this.byLen = {};
};

MagicDictionary.prototype.buildDict = function(dictionary) {
    for (var i = 0; i < dictionary.length; i++) {
        var w = dictionary[i];
        (this.byLen[w.length] = this.byLen[w.length] || []).push(w);
    }
};

MagicDictionary.prototype.search = function(searchWord) {
    var words = this.byLen[searchWord.length] || [];
    for (var i = 0; i < words.length; i++) {
        var diff = 0;
        for (var k = 0; k < searchWord.length && diff < 2; k++) if (words[i][k] !== searchWord[k]) diff++;
        if (diff === 1) return true;
    }
    return false;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Implement Router Medium
• Design Task Manager Medium
• Frequency Tracker Medium
• Find Consecutive Integers from a Data Stream Medium
• Design Memory Allocator Medium
• Longest Uploaded Prefix Medium