52ms C++ Solution beats 99%!


  • 0
    D

    In this problem I encode the each word using a vector whose length is 26. For a given word, the i-th item indicates the number of times the i-th character in the alphabet occurs in the word.

    vector<vector<string>> groupAnagrams(vector<string>& strs)
    {
    	unordered_map<string, vector<string>> map;
    	for(int i = 0; i < strs.size(); i++)
    	{
    		string temp(26,0);
    		for(int j = 0; j < strs[i].length(); j++)
    			temp[strs[i][j] - 'a']++;
    		if(map.count(temp))
    			map[temp].push_back(strs[i]);
    		else
    		{
    			vector<string> group;
    			group.push_back(strs[i]);
    			map[temp] = group;
    		}
    	}
    	vector<vector<string>> ret;
    	for(unordered_map<string, vector<string>>::iterator i = map.begin(); i != map.end(); i++)
    		ret.push_back(i->second);
    	return ret;
    }
    

  • 0
    A

    @dahuang Lack of collision handling. Theoratically not correct.
    Eg. given a string A, consisted by 257 'a', and other string B, consisted by 1 'a'.
    You have a collision and since there is no collision handling at all, your output would be totally wrong.

    The essence of hashing is collision detection and handling.


Log in to reply
 

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