题解 | #牛客代码自动补全#

模拟实现

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param dict string字符串vector 
     * @param strings string字符串vector 
     * @return string字符串vector<vector<>>
     */
    vector<vector<string> > typeahead(vector<string>& dict, vector<string>& strings) {
        int n = dict.size();
        unordered_map<char, map<int,set<int>>> m{};
        //存储每一个字符的字典位置和字符串的下标
        for (int i = 0; i < n; i++) {
            int strlength = dict[i].size();
            for (int j = 0; j < strlength; j++) {
                m[dict[i][j]][i].insert(j);
            }
        }
        vector<vector<string> > res{};
        for (auto& sitem : strings) {
            int slength = sitem.size();
            vector<string> resItem{};
            map<int,set<int>> pres{}; //查询字符串首字母，字典位置和字符串的下标
            for (int i = 0; i < slength; i++) {
                if(i > 0) {
                    for (auto& mitem : pres) {
                        int xb = mitem.first;
                        set<int> titem = mitem.second;
                        for (auto& t1 : titem) {
                             //删除不符合的数据
                             if(t1+i >= dict[xb].size() || dict[xb][t1+i] != sitem[i]) {
                                 mitem.second.erase(t1);
                             }
                        }
                    }
                }
                if(i == 0) {
                  pres = m[sitem[i]];
                }
            }
            for (auto& pitem : pres) {
                if (pitem.second.size() > 0) {
                   //如果pres还有数据则必定符合
                   resItem.push_back(dict[pitem.first]);
                }
            }
            res.push_back(resItem);
        }
        return res;
    }
};