leetcode

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 };