problemmediumalgorithmsleetcode-676leetcode 676leetcode676

Implement Magic Dictionary

MediumUpdated: Aug 2, 2025
Practice on:
LeetCode

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.

Examples

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.

Solution

Method 1 – Trie with DFS Search

Intuition

We want to efficiently check if a word can be transformed into a dictionary word by changing exactly one character. Using a Trie allows fast prefix lookups, and DFS lets us try changing each character in the search word.

Approach

  1. Build a Trie from the dictionary words.
  2. For search, use DFS to traverse the Trie:
    • At each character, try both matching the current character and changing it (if not already changed).
    • Only allow exactly one character change.
    • If we reach the end of the word and have changed exactly one character, check if it's a valid word in the Trie.
  3. Return true if any path matches, else false.

Code

C++
class MagicDictionary {
    struct TrieNode {
        TrieNode* nxt[26] = {};
        bool end = false;
    } *root;
public:
    MagicDictionary() { root = new TrieNode(); }
    void buildDict(vector<string>& dict) {
        for (auto& w : dict) {
            TrieNode* cur = root;
            for (char c : w) {
                if (!cur->nxt[c - 'a']) cur->nxt[c - 'a'] = new TrieNode();
                cur = cur->nxt[c - 'a'];
            }
            cur->end = true;
        }
    }
    bool search(string w) {
        return dfs(root, w, 0, false);
    }
private:
    bool dfs(TrieNode* node, string& w, int i, bool changed) {
        if (!node) return false;
        if (i == w.size()) return changed && node->end;
        int idx = w[i] - 'a';
        if (node->nxt[idx] && dfs(node->nxt[idx], w, i + 1, changed)) return true;
        if (!changed) {
            for (int j = 0; j < 26; ++j) {
                if (j != idx && node->nxt[j] && dfs(node->nxt[j], w, i + 1, true))
                    return true;
            }
        }
        return false;
    }
};
Go
type TrieNode struct {
    nxt [26]*TrieNode
    end bool
}

type MagicDictionary struct {
    root *TrieNode
}

func Constructor() MagicDictionary {
    return MagicDictionary{root: &TrieNode{}}
}

func (md *MagicDictionary) BuildDict(dict []string) {
    for _, w := range dict {
        cur := md.root
        for _, c := range w {
            idx := c - 'a'
            if cur.nxt[idx] == nil {
                cur.nxt[idx] = &TrieNode{}
            }
            cur = cur.nxt[idx]
        }
        cur.end = true
    }
}

func (md *MagicDictionary) Search(w string) bool {
    var dfs func(*TrieNode, int, bool) bool
    dfs = func(node *TrieNode, i int, changed bool) bool {
        if node == nil {
            return false
        }
        if i == len(w) {
            return changed && node.end
        }
        idx := w[i] - 'a'
        if node.nxt[idx] != nil && dfs(node.nxt[idx], i+1, changed) {
            return true
        }
        if !changed {
            for j := 0; j < 26; j++ {
                if j != int(idx) && node.nxt[j] != nil && dfs(node.nxt[j], i+1, true) {
                    return true
                }
            }
        }
        return false
    }
    return dfs(md.root, 0, false)
}
Java
class MagicDictionary {
    class TrieNode {
        TrieNode[] nxt = new TrieNode[26];
        boolean end = false;
    }
    TrieNode root = new TrieNode();
    public void buildDict(String[] dict) {
        for (String w : dict) {
            TrieNode cur = root;
            for (char c : w.toCharArray()) {
                int idx = c - 'a';
                if (cur.nxt[idx] == null) cur.nxt[idx] = new TrieNode();
                cur = cur.nxt[idx];
            }
            cur.end = true;
        }
    }
    public boolean search(String w) {
        return dfs(root, w.toCharArray(), 0, false);
    }
    private boolean dfs(TrieNode node, char[] w, int i, boolean changed) {
        if (node == null) return false;
        if (i == w.length) return changed && node.end;
        int idx = w[i] - 'a';
        if (node.nxt[idx] != null && dfs(node.nxt[idx], w, i+1, changed)) return true;
        if (!changed) {
            for (int j = 0; j < 26; ++j) {
                if (j != idx && node.nxt[j] != null && dfs(node.nxt[j], w, i+1, true))
                    return true;
            }
        }
        return false;
    }
}
Kotlin
class MagicDictionary {
    class TrieNode {
        val nxt = Array<TrieNode?>(26) { null }
        var end = false
    }
    private val root = TrieNode()
    fun buildDict(dict: Array<String>) {
        for (w in dict) {
            var cur = root
            for (c in w) {
                val idx = c - 'a'
                if (cur.nxt[idx] == null) cur.nxt[idx] = TrieNode()
                cur = cur.nxt[idx]!!
            }
            cur.end = true
        }
    }
    fun search(w: String): Boolean = dfs(root, w, 0, false)
    private fun dfs(node: TrieNode?, w: String, i: Int, changed: Boolean): Boolean {
        if (node == null) return false
        if (i == w.length) return changed && node.end
        val idx = w[i] - 'a'
        if (node.nxt[idx] != null && dfs(node.nxt[idx], w, i+1, changed)) return true
        if (!changed) {
            for (j in 0 until 26) {
                if (j != idx && node.nxt[j] != null && dfs(node.nxt[j], w, i+1, true))
                    return true
            }
        }
        return false
    }
}
Python
class TrieNode:
    def __init__(self):
        self.nxt = [None] * 26
        self.end = False

class Solution:
    def __init__(self):
        self.root = TrieNode()
    def buildDict(self, dict: list[str]) -> None:
        for w in dict:
            cur = self.root
            for c in w:
                idx = ord(c) - ord('a')
                if not cur.nxt[idx]:
                    cur.nxt[idx] = TrieNode()
                cur = cur.nxt[idx]
            cur.end = True
    def search(self, w: str) -> bool:
        def dfs(node: TrieNode, i: int, changed: bool) -> bool:
            if not node:
                return False
            if i == len(w):
                return changed and node.end
            idx = ord(w[i]) - ord('a')
            if node.nxt[idx] and dfs(node.nxt[idx], i+1, changed):
                return True
            if not changed:
                for j in range(26):
                    if j != idx and node.nxt[j] and dfs(node.nxt[j], i+1, True):
                        return True
            return False
        return dfs(self.root, 0, False)
Rust
struct TrieNode {
    nxt: [Option<Box<TrieNode>>; 26],
    end: bool,
}

impl TrieNode {
    fn new() -> Self {
        Self { nxt: Default::default(), end: false }
    }
}

struct Solution {
    root: Box<TrieNode>,
}

impl Solution {
    fn new() -> Self {
        Self { root: Box::new(TrieNode::new()) }
    }
    fn build_dict(&mut self, dict: Vec<String>) {
        for w in dict {
            let mut cur = &mut self.root;
            for c in w.chars() {
                let idx = (c as u8 - b'a') as usize;
                cur = cur.nxt[idx].get_or_insert_with(|| Box::new(TrieNode::new()));
            }
            cur.end = true;
        }
    }
    fn search(&self, w: String) -> bool {
        fn dfs(node: &TrieNode, w: &[u8], i: usize, changed: bool) -> bool {
            if i == w.len() {
                return changed && node.end;
            }
            let idx = (w[i] - b'a') as usize;
            if let Some(ref n) = node.nxt[idx] {
                if dfs(n, w, i+1, changed) {
                    return true;
                }
            }
            if !changed {
                for j in 0..26 {
                    if j != idx {
                        if let Some(ref n) = node.nxt[j] {
                            if dfs(n, w, i+1, true) {
                                return true;
                            }
                        }
                    }
                }
            }
            false
        }
        dfs(&self.root, w.as_bytes(), 0, false)
    }
}
TypeScript
class TrieNode {
  nxt: (TrieNode | null)[] = Array(26).fill(null);
  end = false;
}

class Solution {
  root = new TrieNode();
  buildDict(dict: string[]): void {
    for (const w of dict) {
      let cur = this.root;
      for (const c of w) {
        const idx = c.charCodeAt(0) - 97;
        if (!cur.nxt[idx]) cur.nxt[idx] = new TrieNode();
        cur = cur.nxt[idx]!;
      }
      cur.end = true;
    }
  }
  search(w: string): boolean {
    const dfs = (node: TrieNode | null, i: number, changed: boolean): boolean => {
      if (!node) return false;
      if (i === w.length) return changed && node.end;
      const idx = w.charCodeAt(i) - 97;
      if (node.nxt[idx] && dfs(node.nxt[idx], i+1, changed)) return true;
      if (!changed) {
        for (let j = 0; j < 26; ++j) {
          if (j !== idx && node.nxt[j] && dfs(node.nxt[j], i+1, true)) return true;
        }
      }
      return false;
    };
    return dfs(this.root, 0, false);
  }
}

Complexity

  • ⏰ Time complexity: O(n * l * 26) — For each search, we may try changing each of l characters in a word of length l, and for each, try 25 alternatives. n is the number of words in the dictionary.
  • 🧺 Space complexity: O(n * l) — Trie stores all words, each of length l.

Comments