aboutsummaryrefslogtreecommitdiff
path: root/search_suggestion_sys.cpp
blob: 404c987969b5118789a13306e3aa7e15577afbba (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include "leetcode.h"
#include <vector>

class Solution {
public:
  vector<vector<string>> suggestedProducts(vector<string> &products,
                                           string searchWord) {
    auto it = products.begin();
    sort(it, products.end());
    vector<vector<string>> ans;
    string curr = "";
    for (char c : searchWord) {
      curr += c;
      vector<string> suggested;
      it = lower_bound(it, products.end(), curr);
      for (int i = 0; i < 3 && it + i != products.end(); i++) {
        string &s = *(it + i);
        if (s.find(curr))
          break;
        suggested.push_back(s);
      }
      ans.push_back(suggested);
    }
    return ans;
  }
};