【LeetCode75】第七十一题 搜索推荐系统

目录

题目：

示例：

分析：

代码：

---

题目：

示例：

分析：

给我们一个产品数组，以及一个字符串，我们模拟依次输入字符串中的每一个字符，要求返回与对应的输入字符串拥有相同前缀的产品，每次只输出前三个字典序较小的产品。

那么跟前缀有关的题目我们都可以使用前缀树来完成，先用产品数组构建出前缀树，接着按照每次输入进去的字符串对前缀树进行搜索，把搜索到的有相同前缀的字符串中的前三个字典序较小的添加进答案中。

前缀树的具体做法可以参考上一题我写的题解。我这里就不多介绍了。

我个人不太喜欢在刷题的时候额外建一个新的类（因为我懒）。所以我再介绍一种其他做法。

首先对整个产品数组排序，这样后续就不必考虑字典序的问题了。

再我们对输入字符串遍历，来模拟输入的字符串。

接着再对产品进行遍历，如果产品和输入的字符串相同下标的字符不一致，那么表示他们没有相同的前缀，并且往后再怎么输入其他字符也不会用有同样的前缀了，所以可以把这个产品从数组里移除。

遍历结束再向答案数组里塞进前三个产品。

最后对输入遍历完毕我们就获取到了模拟输入产生的效果了。

代码：

class Solution {
public:
    vector> suggestedProducts(vector& products, string searchWord) {
        vector>res;
        sort(products.begin(),products.end());  //提前排序保证字典序
        for(int i=0;isize();i++){   //逐字符输入
            vectortemp;
            int index=0;
            while(indexsize()){   //比较每一个现存产品
                //如果发现同下标的字符不一致,那么后续输入其他字符就更不会有相同前缀了,所以从现存产品中移除
                if(i>=products[index].size() || products[index][i]!=searchWord[i]){ 
                    products.erase(products.begin()+index);
                }else{
                    index++;
                }
            }
            for(int j=0;jsize()&&j<3;j++){    //添加前三个现存产品
                temp.push_back(products[j]);
            }
            res.push_back(temp);
        }        
        return res;
    }
};