This is going to be my first Leetcode post. As a disclaimer: I am by no means an expert. I am, in fact, just trying to learn Leetcode problems and I think this will be a great tool to help solidify the information, tricks, and patterns I learn from doing them.
I am also hoping that if someone stumbles upon this it will be of some help because, personally, the more ways something is explained to me, the better chance I have of understanding it.
Intuition
Use a Dictionary to map each word to its list of anagrams
by sorting each word for easier comparison. Where key is the sorted word and the value is a list of its anagrams contained in the strs array.
Approach
Loop through each word in strs and at each word:
Sort the word.
Check if the dictionary contains the sorted word as a key which would indicate an anagram of that word does exist, and we want to group this one with it.
Add this word to the list of anagrams which is attached to these sorted letters. Where the sorted letters are the dictionary key and the current anagram is added to the corresponding list which is the value attached to the key.
Code
public class Solution
{
public IList<IList<string>> GroupAnagrams(string[] strs)
{
var anagrams = new Dictionary<string, List<string>>();
IList<IList<string>> ans = new List<IList<string>>();
for(int i = 0; i < strs.Length; i++)
{ //get the current word in strs
var temp = strs[i].ToCharArray();
//sort that word. i.e in the first iteration temp will
//be [a, e, t]
Array.Sort(temp);
//convert the word to a string so we can add it to the
//dictionary
var current = new string(temp);
//if this sorted word is in the dictionary then it is
//an anagram of another word with the same letters
if(anagrams.ContainsKey(current))
{
//add the current word (eat) to the list attached to
//the sorted word 'aet'
anagrams[current].Add(strs[i]);
}
else
{
//if there is not a key for this sorted word either
//there is no matching anagram, or we just haven't
//found it yet. So add it to the dictionary
anagrams.Add(current,
new List<string>{strs[i]});
//add the list of anagrams attached to this sorted
//word to the answer we will be returning
ans.Add(anagrams[current]);
}
}
//return the list of lists of anagrams
return ans;
}
}