vivek_ragi

search_suggestions_system

Jul 11th, 2021
1,064
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Custom class Trie with function to get 3 words starting with given prefix
  2. class Trie
  3. {
  4.     // Node definition of a trie
  5.     struct Node {
  6.         bool isWord = false;
  7.         vector<Node *> children{vector<Node *>(26, NULL)};
  8.     } * Root, *curr;
  9.  
  10.     // Runs a DFS on trie starting with given prefix and adds all the words in the result, limiting result size to 3
  11.     void dfsWithPrefix(Node * curr, string & word, vector<string> & result) {
  12.         if (result.size() == 3)
  13.             return;
  14.         if (curr->isWord)
  15.             result.push_back(word);
  16.  
  17.         // Run DFS on all possible paths.
  18.         for (char c = 'a'; c <= 'z'; c++)
  19.             if (curr->children[c - 'a']) {
  20.                 word += c;
  21.                 dfsWithPrefix(curr->children[c - 'a'], word, result);
  22.                 word.pop_back();
  23.             }
  24.     }
  25.  
  26. public:
  27.     Trie() {
  28.         Root = new Node();
  29.     }
  30.     // Inserts the string in trie.
  31.     void insert(string & s) {
  32.         // Points curr to the root of trie.
  33.         curr = Root;
  34.         for (char &c : s) {
  35.             if (!curr->children[c - 'a'])
  36.                 curr->children[c - 'a'] = new Node();
  37.             curr = curr->children[c - 'a'];
  38.         }
  39.         // Mark this node as a completed word.
  40.         curr->isWord = true;
  41.     }
  42.     vector<string> getWordsStartingWith(string & prefix) {
  43.         curr = Root;
  44.         vector<string> result;
  45.  
  46.         // Move curr to the end of prefix in its trie representation.
  47.         for (char &c : prefix) {
  48.             if (!curr->children[c - 'a'])
  49.                 return result;
  50.             curr = curr->children[c - 'a'];
  51.         }
  52.         dfsWithPrefix(curr, prefix, result);
  53.         return result;
  54.     }
  55. };
  56. class Solution {
  57. public:
  58.     vector<vector<string>> suggestedProducts(vector<string> &products,
  59.                                              string searchWord) {
  60.         Trie trie=Trie();
  61.         vector<vector<string>> result;
  62.  
  63.         // Add all words to trie.
  64.         for(string &w:products)
  65.             trie.insert(w);
  66.         string prefix;
  67.         for (char &c : searchWord) {
  68.             prefix += c;
  69.             result.push_back(trie.getWordsStartingWith(prefix));
  70.         }
  71.         return result;
  72.     }
  73. };
RAW Paste Data