49 Group Anagrams – Medium
Problem:
Given an array of strings, group anagrams together.
For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"], Return:
[ ["ate", "eat","tea"], ["nat","tan"], ["bat"] ] Note:
For the return value, each inner list’s elements must follow the lexicographic order. All inputs will be in lower-case.
Thoughts:
Anagrams strings will become the same string after sorting.
Solutions:
public class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
ArrayList<List<String>> result = new ArrayList<List<String>>();
HashMap<String, Integer> helper = new HashMap<String, Integer>();
for (int i = 0; i < strs.length; i ++) {
char[] tmpChar = strs[i].toCharArray();
Arrays.sort(tmpChar);
String tmp = new String(tmpChar);
if (helper.containsKey(tmp)) {
result.get(helper.get(tmp)).add(strs[i]);
continue;
}
List<String> curr = new LinkedList<String>();
curr.add(strs[i]);
result.add(curr);
helper.put(tmp, result.size() - 1);
}
return result;
}
}
There is a concern about the above algorithm is that the hashtable is using String as a key. I am not sure but it could be slow to retrieve a value by using String as key if the String is super long. It depends on how Java is implementing HashTable with String as key. If this is going to be a bottleneck of performance, then use a hash function to hash a String into a integer.