力扣676.实现一个魔法字典

力扣676.实现一个魔法字典

• 字典树 + dfs

•   class Trie{public:Trie* next[26];bool is_end = false;};class MagicDictionary {public:Trie* root = new Trie();void add(string& word){Trie* p = root;for(char c:word){if(p->next[c-'a'] == NULL) p->next[c-'a'] = new Trie();p = p->next[c-'a'];}p->is_end = true;}//idx为下标 ， cnt为可以修改的字符数量 初始为1bool dfs(string& word,int idx,Trie* cur,int cnt){//cnt必须为0，并且字符串必须结束if(idx == word.size()) return cnt == 0 && cur->is_end;for(int i=0;i<26;i++){if(cur->next[i] == NULL) continue;//如果idx位匹配，继续下一个if(i == word[idx] - 'a'){if(dfs(word,idx+1,cur->next[i],cnt)) return true;}//如果idx位不匹配，如果还能修改，就修改继续下一个else if(cnt>0 && dfs(word,idx+1,cur->next[i],cnt-1)) return true;}return false;}void buildDict(vector<string> dictionary) {for(string &word:dictionary)add(word);}bool search(string searchWord) {return dfs(searchWord,0,root,1);}};