Simple C++, easy to understand


  • 0
    W

    class AutocompleteSystem {
    private:
    // sentence -> times
    unordered_map<string, int> mp;
    // cache the current search
    vector<pair<string, int>> cache;
    // current search
    string search;
    // index
    int idx;

    // compares two {sentence, time} pairs
    static bool cmp(pair<string, int>&p1, pair<string, int>&p2){
        if(p1.second == p2.second) return p1.first < p2.first;
        else return p1.second > p2.second;
    }
    

    public:
    AutocompleteSystem(vector<string> sentences, vector<int> times) {
    cache.clear();
    idx = 0;
    search = "";
    for(int i=0; i<sentences.size(); i++){
    mp[sentences[i]] = times[i];
    }
    }

    vector<string> input(char c) {
        vector<string> ans;
        if(c == '#'){
            // end of search, reset variables
            cache.clear();
            idx = 0;
            mp[search]++;
            search = "";
            return ans;
        } else if(idx == 0){
            // first letter in search, compare all entires in map with the letter, store matching {sentence, time} in cache. 
            for(auto &p : mp){
                if(p.first[0] == c) cache.push_back({p.first, p.second});
            }
        } else {
            // following letters, compare entries from cache with the letter, if not match, delete {sentence, time} from cache
            for(int i=0; i<cache.size(); i++){
                if(cache[i].first[idx] != c) {
                    cache.erase(cache.begin()+i);
                    i--;
                }
            }            
        }
        
        idx++; // update idx
        search += c; // update current search
        sort(cache.begin(), cache.end(), cmp); // sort cache 
        
        // output at most 3 results
        for(int k=0; k<cache.size(); k++){
            if(k == 3) break;
            ans.push_back(cache[k].first);
        }
        return ans;
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.