50. 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.
Solution
(1) Java
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String str : strs) {
int[] chars = new int[26];
char[] sc = str.toCharArray();
for (char c : sc) {
chars[c-'a']++;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 26; i++) {
if (chars[i] != 0) {
sb.append('a'+i).append(chars[i]);
}
}
String key = sb.toString();
if (!map.containsKey(key)) {
map.put(key, new ArrayList<String>());
}
map.get(key).add(str);
}
List<List<String>> rst = new ArrayList<>();
for (List<String> list : map.values()) {
rst.add(list);
}
return rst;
}
}
(2) Python
class Solution:
def groupAnagrams(self, strs):
"""
:type strs: List[str]
:rtype: List[List[str]]
"""
cache = {}
for word in strs:
words = ''.join(sorted(word))
if cache.get(words) == None:
cache[words] = []
cache[words].append(word)
rst = []
for l in cache.values():
rst.append(l)
return rst
(3) Scala