Why all solutions used sort? Here's my O(m*n) solution


  • 3
    L

    The idea is to use a customized string as the key of hashmap.

    For example, for abc, I used a1b1c1 as key, which can be formatted in O(n).

    If there are m words, and the average length is n, then this solution is O(mn)

        public List<List<String>> groupAnagrams(String[] strs) {
            Map<String, List<String>> map = new HashMap();
            for(String s: strs){
                String s_count = count(s);
                if(!map.containsKey(s_count)) map.put(s_count, new ArrayList());
                map.get(s_count).add(s);
            }
            return new ArrayList(map.values());
        }
        
        public String count(String s){
            int[] count = new int[26];
            for(char c: s.toCharArray()){
                count[c-'a']++;
            }
            StringBuilder sb = new StringBuilder();
            for(int i=0; i<26; i++){
                if(count[i] > 0) sb.append(count[i]).append((char)(i+'a'));
            }
            return sb.toString();
        }
    

Log in to reply
 

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