LeetCode [49] Group Anagrams

 49. Group Anagrams

Medium

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 lower-case English letters.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

class Solution { public: vector<string> anagrams(vector<string> &strs) { unordered_multimap<string, int> hash; for(int i=0; i<strs.size(); ++i){ string key = strs[i]; sort(key.begin(), key.end()); hash.insert({key, i}); } vector<string> res; for(auto it=hash.begin(); it!=hash.end(); it=hash.equal_range(it->first).second){ if(hash.count(it->first)>1){ auto range = hash.equal_range(it->first); for(auto it=range.first; it!=range.second; ++it){ res.push_back(strs[it->second]); } } } return res; } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14

class Solution { public List<List<String>> groupAnagrams(String[] strs) { if (strs == null || strs.length == 0) return new ArrayList<>(); Map<String, List<String>> map = new HashMap<>(); for (String s : strs) { char[] ca = s.toCharArray(); Arrays.sort(ca); String keyStr = String.valueOf(ca); if (!map.containsKey(keyStr)) map.put(keyStr, new ArrayList<>()); map.get(keyStr).add(s); } return new ArrayList<>(map.values()); } }