C ++中的搜索建议系统
假设我们有一个字符串产品数组和一个名为searchWord的字符串。我们想要设计一个模块,在键入searchWord的每个字符后,最多建议产品列表中的三个产品名称。建议的产品应与searchWord共同使用前缀。当具有共同前缀的三个以上的产品时,返回三个词典最小的产品。因此,我们必须在键入searchWord的每个字符后找到建议产品的列表。
如果输入是:[[“mobile”,“mouse”,“moneypot”,“monitor”,“mousepad”],而searchWord是“mouse”,则输出将是[[“mobile”,“moneypot”,“显示器”],[“移动”,“钱罐”,“显示器”],[“鼠标”,“鼠标垫”],[“鼠标”,“鼠标垫”],[“鼠标”,“鼠标垫”]]
为了解决这个问题,我们将遵循以下步骤-
定义字符串类型键的映射m和字符串值列表
对产品数组p排序
当我在0到p–1的范围内
x:=x+p[i,j]
如果m[x]的长度<3,则将p[i]插入m[x]列表
x:=空字符串
对于范围从0到p[i]–1的长度的j
创建字符串矩阵res,设置temp:=空字符串
当我的范围是0到s的大小–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, ],]