C# || Group Anagrams – How To Group Array Of Anagrams Using C#
The following is a module with functions which demonstrates how to group an array of anagrams using C#.
1. Group Anagrams – Problem Statement
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 1:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Example 2:
Input: strs = [""]
Output: [[""]]
Example 3:
Input: strs = ["a"]
Output: [["a"]]
2. Group Anagrams – Solution
The following is a solution which demonstrates how to group an array of anagrams.
The idea of this solution is to generate a simple hash key for each anagram.
The hash key is made up consisting of a digit, and a letter. These two values represents the character count, and the letter found in the given string.
For example, given the input ["eat","tea","tan","ate","nat","bat"] we create a hash for each anagram as follows:
anagram: eat, hash: 1a1e1t
anagram: tea, hash: 1a1e1t
anagram: tan, hash: 1a1n1t
anagram: ate, hash: 1a1e1t
anagram: nat, hash: 1a1n1t
anagram: bat, hash: 1a1b1t
The hash key is generated similar to the counting sort technique. We use this hash to group the anagrams together.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
// ============================================================================ // Author: Kenneth Perkins // Date: Oct 30, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to group anagrams // ============================================================================ public class Solution { public IList<IList<string>> GroupAnagrams(string[] strs) { var result = new List<IList<string>>(); var seen = new Dictionary<string, List<string>>(); // Go through the anagrams foreach (var anagram in strs) { // Create a hash for this anagram var hash = Hash(anagram); // Check if this hash key exists if (!seen.ContainsKey(hash)) { seen[hash] = new List<string>(); } // Add anagram to matching bucket seen[hash].Add(anagram); } // Build result foreach (var pair in seen) { result.Add(pair.Value); } return result; } private string Hash(string input) { var alphabet = new int[26]; foreach (var ch in input) { ++alphabet[ch - 'a']; } var sb = new StringBuilder(); for (int position = 0; position < alphabet.Length; ++position) { if (alphabet[position] > 0) { sb.Append(alphabet[position]); sb.Append((char)('a' + position)); } } return sb.ToString(); } }// http://programmingnotes.org/ |
QUICK NOTES:
The highlighted lines are sections of interest to look out for.
The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.
Once compiled, you should get this as your output for the example cases:
[["eat","tea","ate"],["tan","nat"],["bat"]]
[[""]]
[["a"]]
Hi, I'm a software engineer. I write articles about programming and design in my spare time.
Leave a Reply