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&nbsp;MagicDictionary&nbsp;class:


	MagicDictionary()&nbsp;Initializes the object.
	void buildDict(String[]&nbsp;dictionary)&nbsp;Sets the data structure&nbsp;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.


&nbsp;
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


&nbsp;
Constraints:


	1 &lt;=&nbsp;dictionary.length &lt;= 100
	1 &lt;=&nbsp;dictionary[i].length &lt;= 100
	dictionary[i] consists of only lower-case English letters.
	All the strings in&nbsp;dictionary&nbsp;are distinct.
	1 &lt;=&nbsp;searchWord.length &lt;= 100
	searchWord&nbsp;consists of only lower-case English letters.
	buildDict&nbsp;will be called only once before search.
	At most 100 calls will be made to search.


class MagicDictionary:

	def __init__(self):
		TrieNode = lambda : defaultdict(TrieNode)
		self.root = TrieNode()

	def buildDict(self, dictionary: List[str]) -> None:
		for s in dictionary:
			cur = self.root
			for c in s: cur = cur[ord(c)-ord('a')]
			cur['$']=True

	def search(self, searchWord: str) -> bool:
		def find(i,cur,mis):
			if i==len(searchWord) and mis==0: return('$' in cur)
			if mis < 0: return False
			if i==len(searchWord) and mis!=0: return False
			ind = ord(searchWord[i])-ord('a')
			ans = False
			for j in range(26):
				if j in cur:
					if(j!=ind):
						ans |= find(i+1,cur[j],mis-1)
					else: ans |= find(i+1,cur[j],mis)
			return ans
			
		return find(0,self.root,1)
class MagicDictionary {
    private String[] dictionary;
    
    public MagicDictionary() {}
    
    public void buildDict(String[] dictionary) {
        this.dictionary = dictionary;
    }
    
    public boolean search(String searchWord) {
        for (String dictWord: this.dictionary) {
            if (this.match(searchWord, dictWord, 1))
                return true;
        }
        
        return false;
    }
    
    private boolean match(String s, String t, int expectedDiff) {
        if (s.length() != t.length())
            return false;
        
        int diff = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != t.charAt(i))
                diff++;
            if (diff > expectedDiff)
                return false;
        }
        
        return diff == expectedDiff;
    }
}

/**
 * Your MagicDictionary object will be instantiated and called as such:
 * MagicDictionary obj = new MagicDictionary();
 * obj.buildDict(dictionary);
 * boolean param_2 = obj.search(searchWord);
 */
struct node{
	bool end = false;
	node *children[26];
};

class MagicDictionary {
public:

	node* root;
	void insert(string&s){
		node* cur = root;
		for(char&c : s){
			if(!cur->children[c-'a']){
				cur->children[c-'a'] = new node();
			}
			cur = cur->children[c-'a'];
		}
		cur->end=true;
	}
	MagicDictionary() {
		root = new node();
	}

	void buildDict(vector<string> dictionary) {
		for(string&s : dictionary)insert(s);
	}
	
	bool find(int i, string& s,node* cur, int mismatch){
		if(i == s.size() and mismatch==0) return cur->end;
		if(mismatch<0)return false;
		if((!cur || i == s.size()) and mismatch!=0) return false;

		int ind = s[i]-'a';
		bool ans = false;
		for(int j=0;j<26;j++){
			if(cur->children[j]){
				if(j!=ind){
					ans |= find(i+1,s,cur->children[j],mismatch-1);
				}else{
					ans |= find(i+1,s,cur->children[j],mismatch);
				}
			}
		}
		return ans;
	}
	bool search(string searchWord) {
		return find(0,searchWord,root,1);
	}
};
function TrieNode(){
    this.children = new Map()
    this.endOfWord = false;
}

var MagicDictionary = function() {
    this.root = new TrieNode()
};

MagicDictionary.prototype.buildDict = function(dictionary) {
    for(let word of dictionary){
        let curr = this.root
        for(let letter of word){
            let map = curr.children
            if(!map.has(letter)) map.set(letter, new TrieNode())
            curr = map.get(letter)
        }
        curr.endOfWord = true
    }
};

MagicDictionary.prototype.search = function(searchWord){
    return  dfs(this.root, searchWord, 0, 0)
}

function dfs(root, str, i, count){
    if(count>1) return false
    if(i==str.length) return count == 1 && root.endOfWord
	
    for(let [char, node] of root.children){
        let c = 0;
        if(char != str[i]) c = 1
        if(dfs(node, str, i+1, count+c)) return true;
    }
    return false
}
Implement Magic Dictionary