leoanjos

Qual o erro, Heitor?

May 25th, 2022 (edited)
188
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.71 KB | None | 0 0
  1. class WordDictionary {
  2. private:
  3.     int nodes;
  4.     vector<int> mx;
  5.     vector<vector<int>> trie;
  6.    
  7. public:
  8.     WordDictionary() {
  9.         nodes = 1;
  10.         mx.push_back(0);
  11.         trie.emplace_back(26, -1);
  12.     }
  13.    
  14.     void addWord(string word) {
  15.         addWord(word, 0, 0);
  16.         cout << mx[0] << "\n";
  17.     }
  18.    
  19.     bool search(string word) {
  20.         return search(word, 0, 0);
  21.     }
  22.    
  23. private:
  24.     int addWord(string &word, int node, int i) {
  25.         cout << node << " " << i << "\n";
  26.         if (i >= (int) word.size()) {
  27.             cout << "returning\n";
  28.             return mx[node] = 1;
  29.         }
  30.        
  31.         char c = word[i];
  32.         if (trie[node][c - 'a'] == -1) {
  33.             mx.push_back(0);
  34.             trie.emplace_back(26, -1);
  35.             trie[node][c - 'a'] = nodes++;
  36.         }
  37.        
  38.         mx[node] = max(mx[node], addWord(word, trie[node][c - 'a'], i + 1) + 1);
  39.         cout << node << " " << mx[node] << "\n";
  40.         return mx[node];
  41.     }
  42.    
  43.     bool search(string &word, int node, int i) {
  44.         if (node == -1) {
  45.             return false;
  46.         }
  47.        
  48.         if (i >= (int) word.size()) {
  49.             return true;
  50.         }
  51.        
  52.         if (word[i] != '.') {
  53.             return search(word, trie[node][word[i] - 'a'], i + 1);
  54.         }
  55.        
  56.         for (char c = 'a'; c <= 'z'; c++) {
  57.             if (search(word, trie[node][c - 'a'], i + 1)) {
  58.                 return true;
  59.             }
  60.         }
  61.  
  62.         return false;
  63.     }
  64. };
  65.  
  66. /**
  67.  * Your WordDictionary object will be instantiated and called as such:
  68.  * WordDictionary* obj = new WordDictionary();
  69.  * obj->addWord(word);
  70.  * bool param_2 = obj->search(word);
  71.  */
Add Comment
Please, Sign In to add comment