Description:
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.
Examples:
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"]]Solution in Python:
To solve the problem of grouping anagrams, we can use a dictionary to map sorted versions of the strings to lists of anagrams.
Python
from typing import List
from collections import defaultdict
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
# Create a default dictionary to hold lists of anagrams
anagrams = defaultdict(list)
# Iterate over each string in the input list
for s in strs:
# Sort the string and use it as a key
key = tuple(sorted(s))
# Append the original string to the list of its anagram group
anagrams[key].append(s)
# Return the values of the dictionary as a list of lists
return list(anagrams.values())Detailed Comments:
- Importing Modules:
Listfromtypingis used for type hints to indicate that the function accepts a list of strings and returns a list of lists of strings.defaultdictfromcollectionsis used to automatically initialize the dictionary with lists.
- Creating the Solution Class:
- The
Solutionclass contains thegroupAnagramsmethod.
- The
- Defining the
groupAnagramsMethod:- We initialize a
defaultdictnamedanagramswithlistas the default factory. This means if a key is not present, it will be initialized as an empty list. - We iterate through each string in the input list
strs. - For each string
s, we create a sorted tuple of its characters usingtuple(sorted(s)). This tuple serves as a unique key for all anagrams of the string. - We append the original string
sto the list corresponding to its sorted tuple key in theanagramsdictionary. - After processing all strings, we return the values of the
anagramsdictionary.list(anagrams.values())converts the dictionary values into a list of lists, which is the desired output.
- We initialize a
This approach ensures that all anagrams are grouped together efficiently, and it runs in O(N⋅Klog K)O(N⋅Klog K) time complexity, where N is the number of strings and K is the maximum length of a string in the input list.
Solution in Javascript:
JavaScript
/**
* @param {string[]} strs
* @return {string[][]}
*/
var groupAnagrams = function(strs) {
// Create a Map to hold lists of anagrams
const anagrams = new Map();
// Iterate over each string in the input array
for (let s of strs) {
// Sort the string and use it as a key
let key = s.split('').sort().join('');
// If the key does not exist in the map, create a new entry with an empty array
if (!anagrams.has(key)) {
anagrams.set(key, []);
}
// Append the original string to the list of its anagram group
anagrams.get(key).push(s);
}
// Return the values of the map as a list of lists
return Array.from(anagrams.values());
};Solution in Java:
Java
import java.util.*;
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
// Create a HashMap to hold lists of anagrams
Map<String, List<String>> anagrams = new HashMap<>();
// Iterate over each string in the input array
for (String s : strs) {
// Convert the string to a character array, sort it, and convert it back to a string
char[] charArray = s.toCharArray();
Arrays.sort(charArray);
String key = new String(charArray);
// If the key does not exist in the map, create a new entry with an empty list
if (!anagrams.containsKey(key)) {
anagrams.put(key, new ArrayList<>());
}
// Append the original string to the list of its anagram group
anagrams.get(key).add(s);
}
// Return the values of the map as a list of lists
return new ArrayList<>(anagrams.values());
}
}Solution in C#:
C#
using System;
using System.Collections.Generic;
public class Solution {
public IList<IList<string>> GroupAnagrams(string[] strs) {
// Create a Dictionary to hold lists of anagrams
Dictionary<string, List<string>> anagrams = new Dictionary<string, List<string>>();
// Iterate over each string in the input array
foreach (string s in strs) {
// Convert the string to a character array, sort it, and convert it back to a string
char[] charArray = s.ToCharArray();
Array.Sort(charArray);
string key = new string(charArray);
// If the key does not exist in the dictionary, create a new entry with an empty list
if (!anagrams.ContainsKey(key)) {
anagrams[key] = new List<string>();
}
// Append the original string to the list of its anagram group
anagrams[key].Add(s);
}
// Return the values of the dictionary as a list of lists
return new List<IList<string>>(anagrams.Values);
}
}