Straightforward O(N) non-sort solution with comments


  • 1
    G

    If we want to use array as key of Java's Map, array has to be converted into List, then it will work as we expected.

    public List<List<String>> groupAnagrams(String[] strs) {
            Map<List<Integer>, List<String>> map = new HashMap<>();
            for (String str : strs) {
                Integer[] k = new Integer[26];
                // Initialize to 0, otherwise each element is null.
                Arrays.fill(k, 0); 
                // Do statistics
                for (int i = 0; i < str.length(); i++) {
                    k[str.charAt(i) - 'a']++;
                }
                // Build the key based on k.
                List<Integer> key = Arrays.asList(k);
                if (!map.containsKey(key)) map.put(key, new ArrayList<>());
                map.get(key).add(str);
            }
    
            List<List<String>> ans = new ArrayList<>();
            ans.addAll(map.values());
            return ans;
        }
    

  • 0
    E

    thx, I was inspired by your solution, but I use hash code of the counter array as the key of map

    public int getID(String s){
    int[] counter = new int[26];
    for(char ch : s.toCharArray()){
    counter[ch - 'a']++;
    }

        return Arrays.hashCode(counter);    //use the counter array's hash code as this anagram's ID
    }
    
    //solution 4, 18ms
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> groups   =   new ArrayList<>();
        Map<Integer, List<String>> anagramMap   =   new HashMap<>();
        
        for(String word : strs){
            int id   =   getID(word);   //unique for each anagram
            List<String> group  =   anagramMap.get(id);
            
            if(null == group){
                group  =   new ArrayList();
                anagramMap.put(id, group);
           
            }
            
            group.add(word);
        }
        
        groups.addAll(anagramMap.values());
        
        return groups;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.