leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1268.cpp (1806B)

      1 
      2 // Original idea
      3 class Solution {
      4   public:
      5     vector<vector<string>> suggestedProducts(vector<string> &products, const string &searchWord) {
      6         sort(begin(products), end(products));
      7 
      8         vector<vector<string>> res(searchWord.size());
      9         for (int i = 0; i < searchWord.size(); i++) {
     10             const string search = searchWord.substr(0, i + 1);
     11             vector<string> found;
     12             for (const auto &product : products) {
     13                 if (product.size() > i && product[i] == searchWord[i])
     14                     found.push_back(product);
     15                 else if (found.size())
     16                     break;
     17             }
     18             for (int k = 0; k < min(3ul, found.size()); k++)
     19                 res[i].push_back(found[k]);
     20             products = found;
     21         }
     22 
     23         return res;
     24     }
     25 };
     26 
     27 // Optimized range based solution
     28 class Solution {
     29   public:
     30     vector<vector<string>> suggestedProducts(vector<string> &products, const string searchWord) {
     31         sort(begin(products), end(products));
     32         vector<vector<string>> res(searchWord.size());
     33         int start = 0, end = products.size();
     34         for (int i = 0; i < searchWord.size(); i++) {
     35             const string search = searchWord.substr(0, i + 1);
     36             bool found = false;
     37             for (int j = start; j < end; j++) {
     38                 if (products[j].size() > i && products[j][i] == searchWord[i]) {
     39                     if (!found) start = j;
     40                     found = true;
     41                 } else if (found) {
     42                     end = j;
     43                     break;
     44                 }
     45             }
     46             if (!found || start >= end) break;
     47             for (int j = 0; j < min(3, end - start); j++)
     48                 res[i].push_back(products[start + j]);
     49         }
     50 
     51         return res;
     52     }
     53 };