4ms c++ solution with brief explanation


  • 0
    W

    map every string to a pattern (all characters - first character + 'a'), if <0, add 26.

    //O(M*N),O(M*N)
    class Solution {
    public:
    //"ba"-> 1,0+26; "az" -> 0,25
        vector<vector<string>> groupStrings(vector<string>& strings) {
            vector<vector<string>> res;
            unordered_map<string,vector<string>> smap;
            //always minus the first letter to make the pattern
            //if < 0, + 26
            for(int i=0;i<strings.size();i++){
                 string pattern;
                 for(int j=0;j<strings[i].size();j++){
                     int index = strings[i][j] - strings[i][0];
                     if(index<0) index+=26;
                     pattern.push_back(index+'a');
                 }
                 smap[pattern].push_back(strings[i]);
            }
            
            for(auto iter = smap.begin();iter != smap.end();iter++)
                res.push_back(iter->second);
            
            
            return res;
        }
    };
    

Log in to reply
 

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