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
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.
Solutions
Solution 1: Trie + DFS
We can use a trie to store all the words in the dictionary. For each word we search, we use depth-first search. Specifically, we start from the root of the trie. For the current letter we are traversing, we first check whether there is a child node that is the same as it. If there is, we continue to traverse downwards. Otherwise, we need to check whether there are remaining modification times. If not, it means that it cannot be matched, so we return false. If there are remaining modification times, we can try to modify the current letter and continue to traverse downwards. If the child node corresponding to the modified letter exists, it means that it can be matched, otherwise it means that it cannot be matched, so we return false. If we traverse to the end of the word and the number of modifications is exactly 1, it means that it can be matched, so we return true.
The time complexity is $O(n \times l + q \times l \times |\Sigma|)$, and the space complexity is $O(n \times l)$, where $n$ and $l$ are the number of words in the dictionary and the average length of the words, respectively, and $q$ is the number of words searched. In addition, $|\Sigma|$ represents the size of the character set. Here, the character set is lowercase English letters, so $|\Sigma|=26$.
classTrie:__slots__="children","is_end"def__init__(self):self.children:List[Optional[Trie]]=[None]*26self.is_end=Falsedefinsert(self,w:str)->None:node=selfforcinw:idx=ord(c)-ord("a")ifnode.children[idx]isNone:node.children[idx]=Trie()node=node.children[idx]node.is_end=Truedefsearch(self,w:str)->bool:defdfs(i:int,node:Optional[Trie],diff:int)->bool:ifi==len(w):returndiff==1andnode.is_endj=ord(w[i])-ord("a")ifnode.children[j]anddfs(i+1,node.children[j],diff):returnTruereturndiff==0andany(node.children[k]anddfs(i+1,node.children[k],1)forkinrange(26)ifk!=j)returndfs(0,self,0)classMagicDictionary:def__init__(self):self.trie=Trie()defbuildDict(self,dictionary:List[str])->None:forwindictionary:self.trie.insert(w)defsearch(self,searchWord:str)->bool:returnself.trie.search(searchWord)# Your MagicDictionary object will be instantiated and called as such:# obj = MagicDictionary()# obj.buildDict(dictionary)# param_2 = obj.search(searchWord)
classTrie{privateTrie[]children=newTrie[26];privatebooleanisEnd;publicvoidinsert(Stringw){Trienode=this;for(charc:w.toCharArray()){inti=c-'a';if(node.children[i]==null){node.children[i]=newTrie();}node=node.children[i];}node.isEnd=true;}publicbooleansearch(Stringw){returndfs(w,0,this,0);}privatebooleandfs(Stringw,inti,Trienode,intdiff){if(i==w.length()){returndiff==1&&node.isEnd;}intj=w.charAt(i)-'a';if(node.children[j]!=null){if(dfs(w,i+1,node.children[j],diff)){returntrue;}}if(diff==0){for(intk=0;k<26;k++){if(k!=j&&node.children[k]!=null){if(dfs(w,i+1,node.children[k],1)){returntrue;}}}}returnfalse;}}classMagicDictionary{privateTrietrie=newTrie();publicMagicDictionary(){}publicvoidbuildDict(String[]dictionary){for(Stringw:dictionary){trie.insert(w);}}publicbooleansearch(StringsearchWord){returntrie.search(searchWord);}}/** * Your MagicDictionary object will be instantiated and called as such: * MagicDictionary obj = new MagicDictionary(); * obj.buildDict(dictionary); * boolean param_2 = obj.search(searchWord); */
classTrie{private:Trie*children[26];boolisEnd=false;public:Trie(){fill(begin(children),end(children),nullptr);}voidinsert(conststring&w){Trie*node=this;for(charc:w){inti=c-'a';if(!node->children[i]){node->children[i]=newTrie();}node=node->children[i];}node->isEnd=true;}boolsearch(conststring&w){function<bool(int,Trie*,int)>dfs=[&](inti,Trie*node,intdiff){if(i>=w.size()){returndiff==1&&node->isEnd;}intj=w[i]-'a';if(node->children[j]&&dfs(i+1,node->children[j],diff)){returntrue;}if(diff==0){for(intk=0;k<26;++k){if(k!=j&&node->children[k]){if(dfs(i+1,node->children[k],1)){returntrue;}}}}returnfalse;};returndfs(0,this,0);}};classMagicDictionary{public:MagicDictionary(){trie=newTrie();}voidbuildDict(vector<string>dictionary){for(auto&w:dictionary){trie->insert(w);}}boolsearch(stringsearchWord){returntrie->search(searchWord);}private:Trie*trie;};/** * Your MagicDictionary object will be instantiated and called as such: * MagicDictionary* obj = new MagicDictionary(); * obj->buildDict(dictionary); * bool param_2 = obj->search(searchWord); */
typeTriestruct{children[26]*TrieisEndbool}funcNewTrie()*Trie{return&Trie{}}func(t*Trie)Insert(wstring){node:=tfor_,c:=rangew{i:=c-'a'ifnode.children[i]==nil{node.children[i]=NewTrie()}node=node.children[i]}node.isEnd=true}func(t*Trie)Search(wstring)bool{vardfsfunc(int,*Trie,int)booldfs=func(iint,node*Trie,diffint)bool{ifi>=len(w){returndiff==1&&node.isEnd}j:=int(w[i]-'a')ifnode.children[j]!=nil&&dfs(i+1,node.children[j],diff){returntrue}ifdiff==0{fork:=0;k<26;k++{ifk!=j&&node.children[k]!=nil&&dfs(i+1,node.children[k],1){returntrue}}}returnfalse}returndfs(0,t,0)}typeMagicDictionarystruct{trie*Trie}funcConstructor()MagicDictionary{returnMagicDictionary{trie:NewTrie()}}func(md*MagicDictionary)BuildDict(dictionary[]string){for_,w:=rangedictionary{md.trie.Insert(w)}}func(md*MagicDictionary)Search(searchWordstring)bool{returnmd.trie.Search(searchWord)}/** * Your MagicDictionary object will be instantiated and called as such: * obj := Constructor(); * obj.BuildDict(dictionary); * param_2 := obj.Search(searchWord); */
classTrie{privatechildren:Trie[]=Array(26).fill(null);privateisEnd:boolean=false;constructor(){}insert(w:string):void{letnode:Trie=this;for(constcofw){consti:number=c.charCodeAt(0)-'a'.charCodeAt(0);if(!node.children[i]){node.children[i]=newTrie();}node=node.children[i];}node.isEnd=true;}search(w:string):boolean{constdfs=(i:number,node:Trie,diff:number):boolean=>{if(i>=w.length){returndiff===1&&node.isEnd;}constj:number=w.charCodeAt(i)-'a'.charCodeAt(0);if(node.children[j]&&dfs(i+1,node.children[j],diff)){returntrue;}if(diff===0){for(letk=0;k<26;k++){if(k!==j&&node.children[k]&&dfs(i+1,node.children[k],1)){returntrue;}}}returnfalse;};returndfs(0,this,0);}}classMagicDictionary{privatetrie:Trie;constructor(){this.trie=newTrie();}buildDict(dictionary:string[]):void{for(constwofdictionary){this.trie.insert(w);}}search(searchWord:string):boolean{returnthis.trie.search(searchWord);}}/** * Your MagicDictionary object will be instantiated and called as such: * var obj = new MagicDictionary() * obj.buildDict(dictionary) * var param_2 = obj.search(searchWord) */
usestd::collections::HashMap;#[derive(Clone)]structTrie{children:Vec<Option<Box<Trie>>>,is_end:bool,}implTrie{fnnew()->Self{Trie{children:vec![None;26],is_end:false,}}fninsert(&mutself,word:&str){letmutnode=self;for&chinword.as_bytes(){letindex=(ch-b'a')asusize;node=node.children[index].get_or_insert_with(||Box::new(Trie::new()));}node.is_end=true;}fnsearch(&self,word:&str,diff:i32)->bool{ifword.is_empty(){returndiff==1&&self.is_end;}letindex=(word.as_bytes()[0]-b'a')asusize;ifletSome(child)=&self.children[index]{ifchild.search(&word[1..],diff){returntrue;}}ifdiff==0{for(i,child)inself.children.iter().enumerate(){ifi!=index&&child.is_some(){ifchild.as_ref().unwrap().search(&word[1..],1){returntrue;}}}}false}}structMagicDictionary{trie:Trie,}/** * `&self` means the method takes an immutable reference. * If you need a mutable reference, change it to `&mut self` instead. */implMagicDictionary{fnnew()->Self{MagicDictionary{trie:Trie::new()}}fnbuild_dict(&mutself,dictionary:Vec<String>){forwordindictionary{self.trie.insert(&word);}}fnsearch(&self,search_word:String)->bool{self.trie.search(&search_word,0)}}