题意

给的一个字符串数组products和一个字符串searchWord，在products中找出与字符串searchWord前缀匹配的字符串，如果相匹配的字符串超过三个，只保留字典序最小的三个。
例如：searchWord=abcde，则其前缀有a、ab、abc、abcd、abcde，在products中找出前缀与a、ab、abc、abcd、abcde匹配的字符串。

解法

拿到题目最直观的想法是遍历searchWord，然后在数组中找出与searchWord匹配的字符串

string prefix = "";
for (auto c : searchWord) {
    prefix += c;
    for (auto word : products) {
        if (word.compare(prefix)) {
            match same prefix
            prefix add match word
        }
    }
}
SORT-MATCH-WORD(result)

从上述伪代码中可以时间复杂度基本就是O(n^3)。

排序+二分查找

我们再对searchWord进行分析，原理
假如products有序，searchWord为best，其前缀有b、be、bes、best：

• 当前缀为b时，在遍历products时，可以不用考虑以a、c~z开头的字符串（为啥？因为searchWord是以b开头的，与以a、c~z开头的字符串不可能有共同前缀）；
• 当前缀为be时，在遍历products时，可以不用考虑以ba~bd、bf~bz为前缀的字符串，因为只有前缀为be的字符串能匹配，即满足要求的前缀范围为[be，bf)（be前缀最后一个字符+1）；
• 依次类推，当在products中寻找前缀为searchWord[0..i]的字符串时只需要在有序数组中找到第一次出现前缀为searchWord[0..i]的字符串，及第一次出现searchWord[0..i-1]+ (char)(searchWord[i]+1);
• 时间复杂度为O(nlogn)，空间复杂度为O(1);

详细源代码如下：

class Solution {
public:
    vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
        sort(products.begin(), products.end());
        vector<vector<string>> result;
        for (int l = 0; l < searchWord.size(); ++ l) {
            auto start = lower_bound(products.begin(), products.end(), searchWord.substr(0, l+1));
            auto end = lower_bound(start, min(start+3, products.end()), searchWord.substr(0, l) + (char)(searchWord[l]+1));
            result.push_back(vector<string>(start, end));
        }
        return result;               
    }
};

字典树 hash+array

此题也可以使用字典树去做，建立字典树

struct Trie {
    unordered_map<char, Trie*> next = {};
    vector<string> suggest = {};
};

其中：

• next用于存储字符对应Trie指针，具体可以自行学习字典树；
• suggest用于存储当前字符串前缀；

以题目给出的Example 3为例：

Input: products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"
Output: [["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]

class Solution {
public:
    struct Trie {
        unordered_map<char, Trie*> next = {};
        vector<string> suggest = {};
    };

    vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
        //build trie tree
        Trie *root = new Trie();
        for (auto word : products) {
            Trie *ptr = root;
            for (auto c : word) {
                if (!ptr->next.count(c)) {
                    ptr->next[c] = new Trie();
                }
                ptr = ptr->next[c];
                ptr->suggest.push_back(word);
            }
        }
        //search prefix
        vector<vector<string>> result(searchWord.length());
        for (int i = 0; i < searchWord.length() && root->next.count(searchWord[i]); ++ i) {
            root = root->next[searchWord[i]];
            sort(root->suggest.begin(), root->suggest.end());
            root->suggest.resize(min(3, (int)root->suggest.size()));
            result[i] = root->suggest;
        }
        return result;
    }
};

字典树 hash+heap

将字典树中存储suggest的数组改为最大堆，堆中只保留3个最小元素；

class Solution {
public:
    struct Trie {
        unordered_map<char, Trie*> next = {};
        priority_queue<string> suggest = {};
    };

    vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
        Trie *root = new Trie();
        for (auto word : products) {
            Trie *ptr = root;
            for (auto c : word) {
                if (!ptr->next.count(c)) {
                    ptr->next[c] = new Trie();
                }
                ptr = ptr->next[c];
                ptr->suggest.push(word);
                if (ptr->suggest.size() > 3) {
                    ptr->suggest.pop();
                }
            }
        }

        vector<vector<string>> result(searchWord.length());
        for (int i = 0; i < searchWord.length() && root->next.count(searchWord[i]); ++ i) {
            root = root->next[searchWord[i]];
            vector<string> match(root->suggest.size());
            for (int i = root->suggest.size()-1; i >= 0; -- i) {
                match[i] = root->suggest.top();
                root->suggest.pop();
            }
            result[i] = match;
        }
        return result;
    }
};