Group Anagrams: Categorizing Words by Character Composition

The "Group Anagrams" problem involves categorizing a list of strings into groups, where each group contains words that are anagrams of each other.

Problem Statement

Given an array of strings, group the anagrams together. 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: ["eat", "tea", "tan", "ate", "nat", "bat"]
• Output: [["ate","eat","tea"], ["nat","tan"], ["bat"]]

Solution Approach - Hashing and Sorting

function groupAnagrams(strs) {
  let map = {};

  for (let str of strs) {
    let sortedStr = str.split("").sort().join("");
    if (!map[sortedStr]) {
      map[sortedStr] = [];
    }
    map[sortedStr].push(str);
  }

  return Object.values(map);
}

Breaking Down the Solution

• Sort and Hash: For each string, sort its characters and use the sorted string as a key in a map.
• Group Anagrams: Group the original strings by their sorted key in the map.
• Result: Return the grouped anagrams as an array of arrays.

Solution in Typescript

function groupAnagrams(strs: string[]): string[][] {
  const map: Record<string, string[]> = {};

  for (const str of strs) {
    // Sort each string to form the key
    const sortedStr = str.split("").sort().join("");
    // Group strings by their sorted key
    if (!map[sortedStr]) {
      map[sortedStr] = [];
    }
    map[sortedStr].push(str);
  }

  // Return the grouped anagrams
  return Object.values(map);
}

In this TypeScript solution:

• The function groupAnagrams takes an array of strings.
• A map (Record<string, string[]>) is used to group strings by their sorted form.
• Each string in the input array is split into characters, sorted, and then joined back to form a key.
• The original strings are then grouped in the map based on this key.
• Finally, the function returns the values of the map, which are arrays of anagrams.

This implementation effectively groups anagrams together by using the sorted version of each string as a key, ensuring that all anagrams have the same key and are thus grouped together.

Conclusion

The Group Anagrams problem is an interesting exercise in string manipulation, sorting, and hashing. It demonstrates how to categorize data based on shared characteristics, in this case, the composition of characters.