Implement Magic Dictionary

medium trie design

Problem

buildDict(words) and search(s) returns true iff exactly one char of s differs from some dictionary word.

Inputbuild(['hello','leetcode']); search('hhllo')

OutputTrue

hhllo vs hello differs in exactly one char.

input

class MagicDictionary:
    def __init__(self): self.by_len = {}
    def buildDict(self, words):
        from collections import defaultdict
        self.by_len = defaultdict(list)
        for w in words: self.by_len[len(w)].append(w)
    def search(self, s):
        for w in self.by_len.get(len(s), []):
            if sum(a != b for a, b in zip(s, w)) == 1: return True
        return False

class MagicDictionary {
  constructor() { this.byLen = new Map(); }
  buildDict(words) {
    this.byLen = new Map();
    for (const w of words) { if (!this.byLen.has(w.length)) this.byLen.set(w.length, []); this.byLen.get(w.length).push(w); }
  }
  search(s) {
    for (const w of (this.byLen.get(s.length) || [])) {
      let diff = 0;
      for (let i = 0; i < s.length && diff < 2; i++) if (s[i] !== w[i]) diff++;
      if (diff === 1) return true;
    }
    return false;
  }
}

class MagicDictionary {
    Map> byLen = new HashMap<>();
    public void buildDict(String[] words) {
        byLen.clear();
        for (String w : words) byLen.computeIfAbsent(w.length(), k -> new ArrayList<>()).add(w);
    }
    public boolean search(String s) {
        for (String w : byLen.getOrDefault(s.length(), new ArrayList<>())) {
            int diff = 0;
            for (int i = 0; i < s.length() && diff < 2; i++) if (s.charAt(i) != w.charAt(i)) diff++;
            if (diff == 1) return true;
        }
        return false;
    }
}

class MagicDictionary {
    unordered_map> byLen;
public:
    void buildDict(vector words) {
        byLen.clear();
        for (auto& w : words) byLen[w.size()].push_back(w);
    }
    bool search(string s) {
        if (!byLen.count(s.size())) return false;
        for (auto& w : byLen[s.size()]) {
            int diff = 0;
            for (int i = 0; i < (int)s.size() && diff < 2; i++) if (s[i] != w[i]) diff++;
            if (diff == 1) return true;
        }
        return false;
    }
};

Explanation

A match here means the query and some dictionary word have the same length and differ in exactly one character. The first useful shortcut is that only words of equal length can ever match, so we bucket the dictionary by length.

In buildDict we group every word into by_len[length]. Then search(s) only looks at the bucket by_len[len(s)] — there is no point comparing strings of different sizes.

For each candidate of the right length, we count how many positions differ. If that count is exactly 1, we have found a match and return true. Zero differences (the same word) or two-plus differences do not count.

Example: dictionary ['hello', 'leetcode'], query 'hhllo'. Only hello shares its length. Comparing position by position: h=h, h≠e (1 diff), l=l, l=l, o=o. Exactly one mismatch, so the answer is True.

Each query compares against the same-length words character by character, giving O(N·L) in the worst case.

Time: O(N·L) per query Space: O(N·L)