Group Anagrams solution with explanation:Leetcode solution

what is Anagrams?

suppose we have two strings and the characters present in both of the strings are same. then both will be called anagram of each other.

eg:" rat" and "art" both are anagram of each other. the characters present in both string are same.

eg: "raat" and "art" these are not anagrams of each other. and the reason is that the frequency of "a" in "raat" is 2. while the frequency of "a" in "art" is 1. so these are not anagrams of each other. in short two strings will be anagram of each other if they have same characters and the count(frequency) of each and every character must be same in both strings.

Solution:

There are different ways to solve this question, so here we are going to use Hashmap to solve this question. cause whenever there is need to search we should go with the data structure which use balanced binary tress or hashing. and we know that Hashmap  uses balanced binary trees. so using this will be a good choice.

now lets talk about the question. we have a vector or array of string. and we have to return a 2D vector or array in which each row will have their anagrams.

now lets's solve it. first create a 2D vector and then create a Hashmap in which there will be a key and a value, so the string itself will be the key and value will be a vector of integer, you will understand it why we are taking a vector of int in the value field.

now we have hashmap and a 2D vector. and we have given a vector of string, in first step we will iterate the whole vector of string by using a for loop. then for each "int i" we will take a temporary string temp. and assign temp=str[i];

now we sort this temp string and search it in the hashmap. if the string is already present in the hashmap. then we will simply add that index into vector of int in the hashmap. and if the string is already not present in the hashmap then we will insert the string and the index of the string into the hasmap.

now traverse the whole hashmap and push value of strings which are present in the vector of int. that will be anagrams of each others.

code:

class Solution {
public:

vector<vector<string>> groupAnagrams(vector<string>& strs) {
       vector<vector<string>>res;
    map<string,vector<int>>m;
    for(int i=0;i<strs.size();i++){
        string s=strs[i];//temp string
        sort(s.begin(),s.end());
        if(m.find(s)!=m.end()){
            auto it = m.find(s);//it->second is a vector
            it->second.push_back(i);//we are pushing index into vector
        }
        else{
        m.insert(make_pair(s,vector<int>{i}));
        }
    }
    for(auto it=m.begin();it!=m.end();it++){//basically we are going through each key and then accessing the vector of int part.
        vector<string>ans;
        for(int i=0;i<it->second.size();i++){
            ans.push_back(strs[it->second[i]]);
        }
        res.push_back(ans);
    }
    return res;
    }
};