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"]]
Constraints:
1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] consists of lowercase English letters.
SOLUTION:
Firstly let's define an Anagram.
Two strings are said to be anagrams of each other if they are made up of the same characters with the same frequency. For example: EAT and TEA. With this definition in mind, we need to group all the anagrams together, and form a resultant output.
Method 1: Brute Force we can iterate over each string in the input array, For each string, check with each element of the array if they are anagrams.
This method will work but we will run out of time trying to execute it for significant test cases.
Method 2: Group by Sorting
One way to solve this problem is to group via sorting. Think about the properties of anagrams. If two words are anagrams of each other, they contain exactly the same characters. So, if we sort both of them, we should theoretically get the exact same string.(Time Comp:O(n∗logk))
Method 3: Improve method 2
It is however possible to improve the above approach a little bit. We can also take advantage of the fact that two anagrams have the same frequency of characters. So, instead of sorting the strings, we can also generate a new string to exhibit this property.
The word KNEE and KEEN are anagrams. You can also say that both these words have K - 1 time, E - 2 times and N - 1 time. Using this method we can create some kind of a frequency string which can be something like E2K1N1. Notice that this string would be identical for both the words.
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
//Keep a table to group all the anagrams together
Map<String, List<String>> map = new HashMap<>();
for(String str : strs){
//Sort the string to get the key
String key = generateKey(str);
//Add the current string to the current table
if(!map.containsKey(key)){
map.put(key, new LinkedList<>());
}
List<String> list = map.get(key);
list.add(str);
}
return new ArrayList<>(map.values());
}
private String generateKey(String str){
int[] map = new int[26];
char[] arr = str.toCharArray();
//O(k) to convert to map {a: 1, b: 0 ....}
for(char curChar : arr){
map[curChar - 'a']++;
}
StringBuilder sb = new StringBuilder();
//O(26) to convert to "1#0#..."
for(int num : map){
sb.append(num);
sb.append("#");
}
return sb.toString();
}
}
If u have a better solution, you can drop it in the comments or leave a link to your repository.