6Companies30days

Group Anagrams

Question - Given an array of strings strs, group the anagrams together. You can return the answer in any order. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Solution

• Only sorting

o(nlogn + wlogw) time

vector<vector<string>> groupAnagrams(vector<string> words) {
	vector <pair <string,int>> wordIndex;
	for( int i = 0 ; i < words.size() ; i++ ){
		wordIndex.push_back({words[i],i});
	}
	
	for( auto & word: wordIndex ) {
		sort(word.first.begin() , word.first.end());
	}
	
	sort( wordIndex.begin(), wordIndex.end());
	
	int i = 0 ;
	
	vector < vector <string>> ret;
	
	while( i < wordIndex.size() ) {
		vector <string> temp;
		temp.push_back( words[wordIndex[i].second]  );
		
		i++;
		
		while( i < wordIndex.size() and wordIndex[i-1].first == wordIndex[i].first ) {
			temp.push_back(words[wordIndex[i].second] );
			i++;
		}
		
		ret.push_back(temp);
	}
	
	
  return ret;
}

• Unorderet set + sorting o(nlogn)

vector<vector<string>> groupAnagrams(vector<string> words) {
  // Write your code here.
	unordered_map <string, vector<string> > dictionary;
	
	for( auto word : words ) {
		auto sortedWord = word;
		sort(sortedWord.begin(), sortedWord.end());
		dictionary[sortedWord].push_back(word);
	} 
	
	vector < vector <string> > ret;
	
	for( auto word : dictionary) {
		ret.push_back(word.second);
	}
	
	
  return ret;
}