nikunjsoni

676

Jun 25th, 2021
103
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Trie{
  2. public:
  3.     Trie* children[26];
  4.     bool end;
  5.     Trie(){
  6.         for(int i=0; i<26; i++)
  7.             children[i] = NULL;
  8.         end = false;
  9.     }
  10. };
  11.  
  12. class MagicDictionary {
  13. private:
  14.     Trie* root = new Trie();
  15. public:
  16.     /** Initialize your data structure here. */
  17.     MagicDictionary() {
  18.        
  19.     }
  20.     void insert(string s){
  21.         Trie* node = root;
  22.         for(char c : s){
  23.             if(!node -> children[c - 'a']){
  24.                 node -> children[c - 'a'] = new Trie();
  25.             }
  26.             node  = node -> children[c - 'a'];
  27.         }
  28.         node -> end = true;
  29.     }
  30.    
  31.     /** Build a dictionary through a list of words */
  32.     void buildDict(vector<string> dict) {
  33.         for(int i = 0; i < dict.size(); i++){
  34.             insert(dict[i]);
  35.         }
  36.     }
  37.    
  38.     bool found(Trie *node, string s, int idx, int change){
  39.         if(idx == s.length() && change && node->end)
  40.             return true;
  41.         else if(idx == s.length())
  42.             return false;
  43.        
  44.         int ch = s[idx]-'a';
  45.         if(change){
  46.             if(node->children[ch])
  47.                 return found(node->children[ch], s, idx+1, change);
  48.             return false;
  49.         }
  50.         else{
  51.             if(node->children[ch] && found(node->children[ch], s, idx+1, 0))
  52.                 return true;
  53.             for(int i=0; i<26; i++){
  54.                 if(i == ch) continue;
  55.                 bool ans = false;
  56.                 if(node->children[i])
  57.                     ans = found(node->children[i], s, idx+1, 1);
  58.                 if(ans) return true;
  59.             }
  60.             return false;
  61.         }
  62.         return false;
  63.     }
  64.    
  65.     /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
  66.     bool search(string word) {
  67.         return found(root, word, 0, 0);
  68.     }
  69. };
  70.  
  71. /**
  72.  * Your MagicDictionary object will be instantiated and called as such:
  73.  * MagicDictionary* obj = new MagicDictionary();
  74.  * obj->buildDict(dict);
  75.  * bool param_2 = obj->search(word);
  76.  */
  77.  
  78.  
  79. ------------------------
  80.  
  81. class MagicDictionary {
  82. public:
  83.     unordered_map<int, vector<string>> memo;
  84.    
  85.     /** Initialize your data structure here. */
  86.     MagicDictionary() {
  87.         memo.clear();
  88.     }
  89.    
  90.     void buildDict(vector<string> dictionary) {
  91.         for (auto & word : dictionary) {
  92.             memo[word.size()].push_back(word);
  93.         }
  94.     }
  95.    
  96.     bool search(string searchWord) {
  97.         int size = searchWord.size();
  98.        
  99.         if (memo.count(size) == 0)
  100.             return 0;
  101.        
  102.         for (auto & word : memo[size]) {
  103.             int cnt = 0;
  104.             for (int i = 0; i < size; ++i) {
  105.                 if (word[i] != searchWord[i]) {
  106.                     cnt++;
  107.                     if (cnt > 1) break;
  108.                 }
  109.             }
  110.             if (cnt == 1)
  111.                 return true;
  112.         }
  113.         return false;
  114.     }
  115. };
  116.  
  117. /**
  118.  * Your MagicDictionary object will be instantiated and called as such:
  119.  * MagicDictionary* obj = new MagicDictionary();
  120.  * obj->buildDict(dictionary);
  121.  * bool param_2 = obj->search(searchWord);
  122.  */
  123.  
RAW Paste Data