18 Lines C++ code (56ms)


  • 1
    R

    First iterate through the vector of string & at each step we do the following:

    • sort the string.
    • if string exist in map then get the index of similar anagram in the result
      otherwise it doesn't exist
    • so add string to the result & it's location to the map.
      ----------------------------------------------------END------------------------------------------------------
      eg :["eat", "tea", "tan", "ate", "nat", "bat"]
    • i = eat
      string sorted = aet;
      it doesn't exist in map so storing it's index in map, i.e., count = 1
      map["aet"] = 1
      now count = 2;
    • i = tea
      string sorted = aet
      it exist in map so map[sorted] = 1 therefore result[1-1].push_back("tea");
      count = 2
      so on...
    class Solution {
    public:
        vector<vector<string>> groupAnagrams(vector<string>& strs) {
            unordered_map<string,int> map;
            vector<vector<string> >result;
            int count=1;//index for caching string location in result
            for(auto i : strs){
                string sorted = i;
                sort(sorted.begin(),sorted.end());
                if(map[sorted] == 0){//sorted  string doesn't exist in map 
                    vector<string> cur(1);
                    cur[0] = i;
                    result.push_back(cur);   //pushing vector of string in result
                    map[sorted] = count++;   //storing index of sorted string
               }
                else//if sorted string already exist push the string
                result[map[sorted]-1].push_back(i);
            }
            return result;
        }
    };
    

    Updated Solution:
    thnks wcyz666 for sharing his idea so that i could his idea to decrease my time & optimize my code time to 56 ms from 60ms using hash function for anagrams.Here is the code:

    class Solution {
    private:
    vector<int> primes = {2, 3, 5, 7, 11 ,13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 107};
    public:
        vector<vector<string>> groupAnagrams(vector<string>& strs) {
            unordered_map<int,int> map;
            vector<vector<string> >result;
            int count=1;
            for(auto i : strs){
                int hash = 1;
    //using hash function instead of sort & caching index in map
                for(int j=0; j < i.size(); ++j){
                    hash *= primes[i[j]-'a'];
                }
                if(map[hash] == 0){
                    vector<string> cur(1);
                    cur[0] = i;
                    result.push_back(cur);
                    map[hash] = count++;
               }
                else
                result[map[hash]-1].push_back(i);
            }
            return result;
        }
    };
    
    

  • 0
    C

    The idea of using the product of different primes as the hash of the string is cool.But why could you put the result at index map[hash]-1 in the result array,I mean different anagram may have the same count ,right?


  • 0
    R

    Because initially map[hash] == 0 so if i start count = 0 how will i be able to differentiate between whether there is any anagram or not.
    yes count can be same for different anagram.
    count is used to check whether anagram already exist or not.
    it it's zero i need to create new vector otherwise i can use it find the index & push that string in same vector.
    index is count-1 as index start from 0 in array whereas count start from 1 (initialized) as it can;t be zero


Log in to reply
 

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