LeetCode 676: Implement Magic Dictionary Solution

Master LeetCode problem 676 (Implement Magic Dictionary), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

676. Implement Magic Dictionary

Medium

Hash Table String Depth-First Search Design Trie

Problem Explanation

Explanation:

To solve this problem, we can use a Trie data structure to store the dictionary words. When searching for a word, we can traverse the Trie and check if we can change exactly one character to match any word in the Trie.

Here's the step-by-step algorithm:

Implement a Trie data structure with the following methods:
- insert(word) to insert a word into the Trie.
- search(word, allowChange) to search for a word in the Trie, allowing one character to be changed if allowChange is true.
Initialize a MagicDictionary class with the Trie data structure and implement the buildDict and search methods.

Time complexity:

Building the Trie: O(N * M), where N is the number of words in the dictionary and M is the average length of a word.
Searching: O(M^2), where M is the length of the search word.

Space complexity: O(N * M) for storing the dictionary words in the Trie.

Solution Code

class TrieNode {
    Map<Character, TrieNode> children;
    boolean isEndOfWord;
    
    public TrieNode() {
        children = new HashMap<>();
        isEndOfWord = false;
    }
}

class Trie {
    TrieNode root;
    
    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            node.children.putIfAbsent(c, new TrieNode());
            node = node.children.get(c);
        }
        node.isEndOfWord = true;
    }
    
    public boolean search(String word, boolean allowChange) {
        return searchHelper(root, word, 0, allowChange, false);
    }
    
    private boolean searchHelper(TrieNode node, String word, int index, boolean allowChange, boolean changed) {
        if (node == null) return false;
        if (index == word.length()) {
            return changed && node.isEndOfWord;
        }
        
        char c = word.charAt(index);
        if (allowChange) {
            for (char child : node.children.keySet()) {
                if (searchHelper(node.children.get(child), word, index + 1, false, changed || child != c)) {
                    return true;
                }
            }
            return false;
        } else {
            return searchHelper(node.children.get(c), word, index + 1, false, changed);
        }
    }
}

class MagicDictionary {
    Trie trie;
    
    public MagicDictionary() {
        trie = new Trie();
    }
    
    public void buildDict(String[] dictionary) {
        for (String word : dictionary) {
            trie.insert(word);
        }
    }
    
    public boolean search(String searchWord) {
        return trie.search(searchWord, true);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 676 (Implement Magic Dictionary)?

This page provides optimized solutions for LeetCode problem 676 (Implement Magic Dictionary) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 676 (Implement Magic Dictionary)?

The time complexity for LeetCode 676 (Implement Magic Dictionary) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 676 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 676 in Java, C++, or Python.

Back to LeetCode Solutions