力扣676.实现一个邪术字典

力扣676.实现一个邪术字典

• 字典树 + dfs
  
• 1.   class Trie
  2.   {
  3.       public:
  4.       Trie* next[26];
  5.       bool is_end = false;
  6.   };
  7.   class MagicDictionary {
  8.   public:
  9.       Trie* root = new Trie();
  10.       
  11.       void add(string& word)
  12.       {
  13.           Trie* p = root;
  14.           for(char c:word)
  15.           {
  16.               if(p->next[c-'a'] == NULL) p->next[c-'a'] = new Trie();
  17.               p = p->next[c-'a'];
  18.           }
  19.           p->is_end = true;
  20.       }
  21.       //idx为下标 ， cnt为可以修改的字符数量 初始为1
  22.       bool dfs(string& word,int idx,Trie* cur,int cnt)
  23.       {
  24.           //cnt必须为0，并且字符串必须结束
  25.           if(idx == word.size()) return cnt == 0 && cur->is_end;
  26.           for(int i=0;i<26;i++)
  27.           {
  28.               if(cur->next[i] == NULL) continue;
  29.               //如果idx位匹配，继续下一个
  30.               if(i == word[idx] - 'a')
  31.               {
  32.                   if(dfs(word,idx+1,cur->next[i],cnt)) return true;
  33.               }
  34.               //如果idx位不匹配，如果还能修改，就修改继续下一个
  35.               else if(cnt>0 && dfs(word,idx+1,cur->next[i],cnt-1)) return true;
  36.           }
  37.           return false;
  38.       }
  39.       void buildDict(vector<string> dictionary) {
  40.           for(string &word:dictionary)
  41.               add(word);
  42.       }
  43.       
  44.       bool search(string searchWord) {
  45.           return dfs(searchWord,0,root,1);
  46.       }
  47.   };

  复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。