Two simple solutions in C++


  • 3
    M

    1.When get new anagram word, save the index in unordered_map. If the anagram exists, insert current word in specific location which comes from binary search method. 64ms.

    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ans;
        unordered_map<string, int> hash;
        string ori;
        for(int i=0; i<strs.size(); i++){
            ori = strs[i];
            sort(ori.begin(), ori.end());
            if(hash.count(ori)>0) {
                int idx = hash[ori];
                int pos = searchInsert(ans[idx], strs[i]); //find specific location
                vector<string>::iterator it = ans[idx].begin()+pos;
                ans[idx].insert(it, strs[i]);
            }
            else {
                hash[ori]=ans.size();
                ans.push_back(vector<string>(1, strs[i]));
            }
        }            
        return ans;
    }
    int searchInsert(vector<string>& a, string target) {
        int lo = 0;
        int hi = a.size() - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (target < a[mid]) hi = mid - 1;
            else if (target > a[mid]) lo = mid + 1;
            else return mid;
        }
        return lo;
    }
    

    2.When get new anagram word, save the index in unordered_map. If the anagram exists, push it into the vector directly. After traversing, sort the ans's different vectors. 64ms.

    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ans;
        unordered_map<string, int> hash;
        string ori;
        for(int i=0; i<strs.size(); i++){
            ori = strs[i];
            sort(ori.begin(), ori.end());
            if(hash.count(ori)>0) {
                ans[hash[ori]].push_back(strs[i]);
            }
            else {
                hash[ori]=ans.size();
                ans.push_back(vector<string>(1, strs[i]));
            }
        }            
        for(int i=0; i<ans.size(); i++){
            sort(ans[i].begin(), ans[i].end()); //can use other method
        }
        return ans;
    }
    

    If you can make the solution better, please leave a answer or a link. Thanks!


Log in to reply
 

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