49. Group Anagrams

GroupAnagrams.cs

public class Solution {
  public IList<IList<string>> GroupAnagrams(string[] strs) {
    var groups = new List<IList<string>>();
    var dict = new Dictionary<string, List<string>>();
    
    string KeyForWord(in string word){
      var freq = Freq(word);
      var sb = new StringBuilder();
      for(var c = 0; c < freq.Length; ++c)
        sb.Append($"{c}-{freq[c]},");
      return sb.ToString();
    }

    foreach(var word in strs){
      var key = KeyForWord(word);
      if(!dict.ContainsKey(key))
        dict[key] = new();
      dict[key].Add(word);
    }
    
    foreach(var words in dict.Values)
      groups.Add(words);
    
    return groups;
  }
  
  private static char[] Freq(in string word){
    var freqs = new char[26];
    foreach(var letter in word)
      freqs[letter - 'a']++;
    return freqs;
  }

  public IList<IList<string>> GroupAnagramsSorting(string[] strs) {
    var groups = new List<IList<string>>();
    var dict = new Dictionary<string, List<string>>();
    
    // O(Kx Log Kx) O(Kx)
    string GetKeyForWord(in string word){
      var chars = word.ToCharArray();
      Array.Sort(chars);
      return new string(chars); 
    }

    foreach(var word in strs){
      var key = GetKeyForWord(word);
      if(!dict.ContainsKey(key))
        dict[key] = new();
      dict[key].Add(word);
    }

    foreach(var words in dict.Values)
      groups.Add(words);
    
    return groups;
  }
}
/*
"eat","tea","tan","ate","nat","bat"
 aet,  aet,  ant,  aet,  ant,  abt


eat -> tea, tan, ate, nat, bat

foreach word
  group.Add(word)
  foreach otherWord
   if word == otherWord
     continue
   if(!isAnagram(word, otherWord))
     continue
   group.Add(otherWord)
  groups.Add(group)

 e   t 
 a e   a
 t a   n
*/