C++での検索候補システム

文字列製品の配列とsearchWordという文字列があるとします。 searchWordの各文字を入力した後、商品リストから最大3つの商品名を提案するモジュールを設計します。提案された製品には、searchWordと共通のプレフィックスが付いている必要があります。共通の接頭辞を持つ製品が3つ以上ある場合は、辞書式順序で最小の3つの製品を返します。したがって、searchWordの各文字を入力した後、提案された製品のリストを見つける必要があります。

入力が["mobile"、 "mouse"、 "moneypot"、 "monitor"、 "mousepad"]のようで、searchWordが "mouse"の場合、出力は[["mobile"、 "moneypot"、 "monitor"]、["mobile"、 "moneypot"、 "monitor"]、["mouse"、 "mousepad"]、["mouse"、 "mousepad"]、["mouse"、 "mousepad"]]

これを解決するには、次の手順に従います-

• 文字列型キーのマップmと文字列値のリストを定義します

• 製品配列pを並べ替える

• 0からp–1のサイズまでの範囲のiの場合

  • x：=空の文字列

  • 0からp[i]– 1

    の長さのjの場合

    • x：=x + p [i、j]

    • m [x] <3の長さの場合、p[i]をm[x]リストに挿入します

• 文字列resの行列を作成し、temp：=empty string

  を設定します

• 0からsのサイズまでの範囲のiの場合– 1

  • temp：=temp + s [i]

  • m[temp]をresに挿入します

• 解像度を返す

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << "[";
      for(int j = 0; j <v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
   cout << "],";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   vector<vector<string>> suggestedProducts(vector<string>& p,
   string s) {
      map <string, vector < string > > m;;
      sort(p.begin(), p.end());
      for(int i = 0; i < p.size(); i++){
         string x = "";
         for(int j = 0; j < p[i].size(); j++){
            x += p[i][j];
            if(m[x].size()<3)m[x].push_back(p[i]);
         }
      }
      vector < vector <string> > res;
      string temp = "";
      for(int i = 0; i < s.size(); i++){
         temp += s[i];
         res.push_back(m[temp]);
      }
      return res;
   }
};
main(){
   vector<string> v =
   {"mobile","mouse","moneypot","monitor","mousepad"};
   Solution ob;
   print_vector(ob.suggestedProducts(v, "mouse"));
}

入力

["mobile","mouse","moneypot","monitor","mousepad"]
"mouse"

出力

[[mobile, moneypot, monitor, ],[mobile, moneypot, monitor, ],[mouse,
mousepad, ],[mouse, mousepad, ],[mouse, mousepad, ],]