Group anagrams

Group words that are anagrams of each other. Sorting each word's letters gives a key that every anagram shares.

The idea

Two words are anagrams exactly when sorting their letters gives the same string. That sorted string is a perfect dictionary key: every word that produces it belongs in the same group, so one pass with a Dictionary<string, List<string>> does all the grouping.

Code

public static List<List<string>> GroupAnagrams(string[] words) {
    var groups = new Dictionary<string, List<string>>();
    foreach (string w in words) {
        var key = new string(w.OrderBy(c => c).ToArray());
        if (!groups.TryGetValue(key, out var list))
            groups[key] = list = new List<string>();
        list.Add(w);
    }
    return groups.Values.ToList();
}

Tips

• Sorting a short word is cheap, and it turns an awkward "do these use the same letters" test into an exact string comparison.
• A 26-length character-count array can serve as the key too, and avoids the O(w log w) sort per word.

In the .NET library

The key never has to be meaningful on its own - it only has to be identical for words that belong together, and different for words that do not. That is the whole job of a hash key.