Clear O(n) C++ solution using hash table


  • 0
    I
    vector<vector<string>> groupStrings(vector<string>& strings) {
        vector<vector<string>> res;
        if(strings.empty())
            return res;
        unordered_map<string, vector<string>> mp; 
        for(int i = 0; i < strings.size(); ++i){
            string str_key = getKey(strings[i]);
            mp[str_key].push_back(strings[i]);
        }
        for(unordered_map<string, vector<string>> :: iterator itr = mp.begin(); itr != mp.end(); ++itr){
            sort(itr->second.begin(), itr->second.end());
            res.push_back(itr->second);
        }
        return res;
    }
    
    string getKey(string str){
        int key = str[0] - 'a';
        for(int i = 0; i < str.size(); ++i){
            if(str[i] - key >= 'a')
                str[i] = str[i] - key;
            else
                str[i] = str[i] - key + 26;
        }
        return str;
    }

Log in to reply
 

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