Leetcode•Sep 21, 2025

Implement Magic Dictionary

Hazrat Ali

Leetcode

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

Solution

class TrieNode {
  constructor() {
    this.children = {};
    this.isEnd = false;
  }
}

class MagicDictionary {
  constructor() {
    this.root = new TrieNode();
  }

  /**
   * @param {string[]} dict
   * @return {void}
   */
  buildDict(dict) {
    dict.forEach(word => {
      this.insert(word);
    });
  }

  insert(word) {
    let current = this.root;
    for (let i = 0; i < word.length; i++) {
      const c = word[i];
      if (!current.children[c]) {
        current.children[c] = new TrieNode();
      }
      current = current.children[c];
    }
    current.isEnd = true;
  }

  /**
   * @param {string} word
   * @return {boolean}
   */
  search(word) {
    const letters = 'abcdefghijklmnopqrstuvwxyz';

    for (let i = 0; i < word.length; i++) {
      for (let j = 0; j < letters.length; j++) {
        const letter = letters[j];

        if (word[i] !== letter) {
          const modifiedWord = word.substr(0, i) + letter + word.substr(i + 1);

          if (this.match(modifiedWord)) {
            return true;
          }
        }
      }
    }

    return false;
  }

  match(word) {
    let current = this.root;
    for (let i = 0; i < word.length; i++) {
      const c = word[i];
      if (!current.children[c]) {
        return false;
      }
      current = current.children[c];
    }
    return current.isEnd;
  }
}

 

Comments