leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1268.cpp (1806B)

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