Description
https://leetcode.com/problems/group-anagrams/
Given an array of strings, group anagrams together.
Example:
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
Note:
- All inputs will be in lowercase.
- The order of your output does not matter.
Explanation
use sorted words to group anagrams
Python Solution
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
result = []
groups = {}
for word in strs:
sorted_word = ''.join(sorted(word))
if sorted_word in groups:
groups[sorted_word].append(word)
else:
groups[sorted_word] = [word]
for key, value in groups.items():
result.append(value)
return result- Time complexity: O(n).
- Space complexity: O(n).
I found that solution very popular and helpful:
https://www.youtube.com/watch?v=n80QtzugEP8&ab_channel=EricProgramming
/**
Solution in java
**/
class Solution
{
public static void main(String[] args)
{
String[] strings = {“cat”, “dog”, “tac”, “god”, “act”};
List output = groupAnagrams(strings);
System.out.println(“output is: “+ output.toString());
}
private static List groupAnagrams(String[] strs)
{
Map map = new HashMap();
for(String str : strs)
{
char[] curr = str.toCharArray();
Arrays.sort(curr);
String tmp = new String(curr);
if(!map.containsKey(tmp))
{
map.put(tmp,new ArrayList());
}
map.get(tmp).add(str);
}
return new ArrayList(map.values());
}
}