Implement Magic Dictionary

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


**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

Build a Trie from the dictionary words.
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.
Return true if any path matches, else false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51


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)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56


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)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


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.

Problem#

Examples#

Example 1#

Constraints#

Solution#

Method 1 – Trie with DFS Search#

Intuition#

Approach#

Code#

Complexity#