Java 20ms solution using counting sort


  • 2
    S

    Given a string "abddb", the most popular solution use "Arrays.sort(['a','b','d','d','b'])" to get the key. This solution has time complexity O(n*(mlog m)). Using the counting sort, the time complexity can be reduced to
    O(n
    (m + 26))

    public class Solution {
            public List<List<String>> groupAnagrams(String[] strs) {
                HashMap<String, List<String>> myMap = new HashMap<String, List<String>>();
                
                for (String str : strs) {
                    String ordered = orderedString(str);
                    if (!myMap.containsKey(ordered)) {
                        myMap.put(ordered, new ArrayList<String>());
                    }
                    
                    myMap.get(ordered).add(str);
                }
                
                for (String key : myMap.keySet()) {
                    Collections.sort(myMap.get(key));
                }
                
                return new ArrayList<List<String>>(myMap.values());
            }
            
            String orderedString(String str) {
                //use count sort O(m + 26) where m = str.length();
                //space
                // if str = "a b b f"
                if (str == null || str.length() == 0) return "";
                char[] output = new char[str.length()];
                int[] count = new int[26];
                
                //count = [1 2 0 0 0 1 0 0... 0]
                for (int i = 0; i < str.length(); i++) {
                    count[str.charAt(i) - 'a'] += 1;
                }
                
                //count = [0 1 3 3 3 3 4 ... 4];
                int preTotal = 0;
                for (int i = 0; i < count.length; i++) {
                    int tmp = count[i];
                    //number of iterm less than i
                    count[i] = preTotal;
                    preTotal += tmp;  
                }
                
                for (int i = 0; i < str.length(); i++) {
                    output[count[str.charAt(i) - 'a']] = str.charAt(i);
                    //next position
                    count[str.charAt(i) - 'a'] += 1;
                }
                
                return new String(output);
               
            }
        }

  • 0
    E

    I have a similar idea, but yours is much faster than mine :)


  • 0
    E

    BTW, you seem to have forgotten to comment out the following line:

    count[str.charAt(i) - 'a'] += 1;

Log in to reply
 

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