[前缀树]leetcode676：实现一个魔法字典(medium)

前缀树]leetcode676：实现一个魔法字典(medium)"/>

[前缀树]leetcode676：实现一个魔法字典(medium)

题目：

题解：

思路1：前缀树 + dfs 枚举

• 这里主要说下 dfs 的枚举逻辑：由于只能替换一个字符并且必须替换，因此需要用一个变量 cnt 来记录替换字符的个数；将 s[idx] 进行替换的话，必须要 root->next 中存在的字符节点才能被 s[idx] 替换。因此对于每个节点，我们从小到大枚举 26 个字符，若该字符存在，则需要判断是否需要替换，与 s[idx] 相同就不需要替换，则继续递归下一个字符 idx+1；与 s[idx] 不同，就可以进行替换，同时这里可以进行剪枝，对于已经替换过的一次的，就不用再进行替换了。剩下的看代码即可

---

思路2：硬模拟

• 对于每个需要替换的字符串 s，直接枚举 dict，看看其中是否有单词与其只有一个字符不同。最大的时间复杂度为 100100100，不会进行超时。

代码如下：

// 2022/7/11：前缀树
class Trie
{
private:bool is_string=false;Trie *next[26]={nullptr};
public:Trie(){}void insert(const string& word)//插入单词{Trie *root=this;for(const auto& w:word){if(root->next[w-'a']==nullptr)root->next[w-'a']=new Trie();root=root->next[w-'a'];}root->is_string=true;}// 使用 dfs 来枚举一种可行方案bool dfs(Trie *root,const string& s,int idx,int cnt){if(s.size()==idx)return root->is_string&&cnt==1;// 当前s[idx]对应的字符数字int u=s[idx]-'a';// 枚举替换某个字母，将s[idx]替换成root->next中某个存在的节点for(int i=0;i<26;++i){// 必须要当前节点存的字符存在才能进行替换或者继续递归if(root->next[i]==nullptr)continue;// root->next中包含s[idx]，则继续进行递归 if(u==i){if(dfs(root->next[i],s,idx+1,cnt))return true;}// root->next中不含s[idx]，则用root->next中存在一个字母i进行替换即可else if(cnt==0&&dfs(root->next[i],s,idx+1,cnt+1))return true;}return false;}
};class MagicDictionary {
public:Trie *root;MagicDictionary() {root=new Trie();}void buildDict(vector<string> words) {for(auto word:words){root->insert(word);}}bool search(string s) {return root->dfs(root,s,0,0);}
};

// 2022/7/11 :硬模拟
class MagicDictionary {
public:vector<string> dict;MagicDictionary() {}void buildDict(vector<string> dict) {this->dict=dict;}// 判断两个单词是否只有一个字符不等bool check(const string& a,const string& b){// 长度不等直接返回falseif(a.size()!=b.size())return false;int cnt=0;for(int i=0,n=a.size();i<n;++i){if(a[i]!=b[i]&&++cnt>1)return false;}return cnt==1;}bool search(string b) {for(const auto &a:dict){if(check(a,b))return true;}return false;}
};