Last updated on July 19th, 2024 at 11:32 pm

Here, We see Implement Magic Dictionary LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

Stack

Companies

LinkedIn

Level of Question

Medium

Implement Magic Dictionary LeetCode Solution

Problem Statement

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

1. Implement Magic Dictionary LeetCode Solution C++

class MagicDictionary {
public:
    unordered_set<string> set;
    MagicDictionary(){
    }
    void buildDict(vector<string> dictionary){
        for(string str: dictionary)
            set.insert(str);
    }
    bool search(string searchWord){
        for(string s: set){
            if(s.size()==searchWord.size()){
                int cnt=0;
                for(int i=0;i<s.size();i++){
                    if(s[i]!=searchWord[i]) cnt++;
                }
                if(cnt==1) return true;
            }
        }
        return false;
    }
};

2. Implement Magic Dictionary LeetCode Solution Java

class MagicDictionary {
    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isWord;
        public TrieNode() {}
    }
    TrieNode root;
    public MagicDictionary() {
        root = new TrieNode();
    }
    public void buildDict(String[] dictionary) {
        for (String s : dictionary) {
            TrieNode node = root;
            for (char c : s.toCharArray()) {
                if (node.children[c - 'a'] == null) {
                    node.children[c - 'a'] = new TrieNode();
                }
                node = node.children[c - 'a'];
            }
            node.isWord = true;
        }
    }
    public boolean search(String searchWord) {
        char[] arr = searchWord.toCharArray();
        for (int i = 0; i < searchWord.length(); i++) {
            for (char c = 'a'; c <= 'z'; c++) {
                if (arr[i] == c) {
                    continue;
                }
                char org = arr[i];
                arr[i] = c;
                if (helper(new String(arr), root)) {
                    return true;
                }
                arr[i] = org;
            }
        }
        return false;
    }
    public boolean helper(String s, TrieNode root) {
        TrieNode node = root;
        for (char c : s.toCharArray()) {
            if (node.children[c - 'a'] == null) {
                return false;
            }
            node = node.children[c - 'a'];
        }
        return node.isWord;
    }
}

3. Implement Magic Dictionary LeetCode Solution JavaScript

var MagicDictionary = function() {
    this.book = new Map();
};
MagicDictionary.prototype.buildDict = function(dictionary) {
    for(let word of dictionary){
        if(this.book.get(word.length)) this.book.get(word.length).push(word);
        else this.book.set(word.length, [word]);
    }
};
MagicDictionary.prototype.search = function(searchWord) {
    if(!this.book.get(searchWord.length)) return false;
    let set = [...this.book.get(searchWord.length)];
    let w = 0;
    while(w<searchWord.length){
        for(let i = 0; i < set.length; i++){
            if(searchWord[w]!==set[i][w]){
                if(searchWord.slice(w+1)===set[i].slice(w+1)) return true;
                set.splice(i,1), i--;
            }}
        w++;
    }
    return false;
};

4. Implement Magic Dictionary LeetCode Solution Python

class MagicDictionary(object):
    def __init__(self):
        self.myDict = defaultdict(set)
    def buildDict(self, dictionary):
        for word in dictionary:
            n = len(word)
            self.myDict[n].add(word)
    def search(self, searchWord):
        n = len(searchWord)
        if n not in self.myDict: return False
        def diff(word1, word2):
            count = 0
            for i in range(len(word1)):
                if word1[i] != word2[i]:
                    count += 1 
                if count > 1:
                    return count
            return count
        for word in self.myDict[n]:
            if diff(word, searchWord) == 1:
                return True
        return False