49. Group Anagrams

Posted on | Edited on | Views:

LeetCode

Approach 1: Categorize by Sorted String, Time Complexity: O(NKlogK)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> map=new HashMap<>();
        for(String str:strs){
            char[] chs=str.toCharArray();
            Arrays.sort(chs);
            String newStr=new String(chs);
            if(!map.containsKey(newStr)) map.put(newStr,new ArrayList(Arrays.asList(str)));
            else map.get(newStr).add(str);
        }
        return new ArrayList(map.values());
    }
}

Approach 2: Categorize by Count, Time Complexity: O(NK)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs.length == 0) return new ArrayList();
        Map<String, List> ans = new HashMap<String, List>();
        int[] count = new int[26];
        for (String s : strs) {
            Arrays.fill(count, 0);
            for (char c : s.toCharArray()) count[c - 'a']++;

            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 26; i++) sb.append(count[i]);
            
            String key = sb.toString();
            if (!ans.containsKey(key)) ans.put(key, new ArrayList());
            ans.get(key).add(s);
        }
        return new ArrayList(ans.values());
    }
}

0%