数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++ 搜索建议系统
假设我们有一个字符串数组 `products` 和一个名为 `searchWord` 的字符串。我们想要设计一个模块，在输入 `searchWord` 的每个字符后，从 `products` 列表中最多建议三个产品名称。建议的产品应该与 `searchWord` 具有共同的前缀。当有多于三个产品具有共同前缀时，返回三个字典序最小的产品。因此，我们必须找到在输入 `searchWord` 的每个字符后建议的产品列表。
如果输入类似：[ "mobile","mouse","moneypot","monitor","mousepad"], 并且 `searchWord` 为 “mouse”，则输出将为 [["mobile","moneypot","monitor"], ["mobile","moneypot","monitor"], ["mouse","mousepad"], ["mouse","mousepad"], ["mouse","mousepad"]]
为了解决这个问题，我们将遵循以下步骤：
定义一个字符串类型键和字符串值列表的映射 `m`
对产品数组 `p` 进行排序
对于 `i` 从 0 到 `p` 的大小减 1
x := 空字符串
对于 `j` 从 0 到 `p[i]` 的长度减 1
x := x + p[i, j]
如果 `m[x]` 的长度小于 3，则将 `p[i]` 插入到 `m[x]` 列表中
创建一个字符串矩阵 `res`，设置 `temp` := 空字符串
对于 `i` 从 0 到 `s` 的大小减 1
temp := temp + s[i]
将 `m[temp]` 插入到 `res` 中
返回 `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, ],]
更新于：2020年5月2日
浏览量：284
广告