49. Group Anagrams

Problem

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 (Java)

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> hm = new HashMap<>();
        for (String s : strs) {
            char[] ch = s.toCharArray();
            Arrays.sort(ch);
            String temp = new String(ch);
            hm.computeIfAbsent(temp, k -> new ArrayList<>());
            hm.get(temp).add(s);
        }
        return (new ArrayList<>(hm.values()));
    }
}

Solution (Javascript)

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
  var res = {};
  var str = '';
  var len = strs.length;
  for (var i = 0; i < len; i++) {
    str = Array.from(strs[i]).sort().join('');
    if (!res[str]) res[str] = [];
    res[str].push(strs[i]);
  }
  return Object.values(res);
};

Explain:

把每个字符串排序一下，用哈希表存起来

Complexity:

• Time complexity : O(m * nlog(n)). m 为数组长度， n 为字符长度。
• Space complexity : O(m).