Share my short JAVA solution


  • 165
    W
    public class Solution {
        public List<List<String>> groupAnagrams(String[] strs) {
            if (strs == null || strs.length == 0) return new ArrayList<List<String>>();
            Map<String, List<String>> map = new HashMap<String, List<String>>();
            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<String>());
                map.get(keyStr).add(s);
            }
            return new ArrayList<List<String>>(map.values());
        }
    }

  • 0
    This post is deleted!

  • 6
    T

    Small suggestion.
    I found out that its much faster to sort individual hashmap buckets than to sort input array whose size is very large..
    Earlier i had not expected this.


  • 17
    Y

    Agree with @sreenidhi2. So I modified the code a little bit: instead of sort the string array at the beginning, I sorted the list of each hashmap bucket at the last step.

    public List<List<String>> groupAnagrams(String[] strs) {
    	if(strs==null || strs.length == 0){
    		return new ArrayList<List<String>>();
    	}
    	HashMap<String, List<String>> map = new HashMap<String, List<String>>();
    	//Arrays.sort(strs);
    	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<String>());
    		map.get(keyStr).add(s);
    	}
    	
    	for(String key: map.keySet()) {
    		Collections.sort(map.get(key));
    	}
    	return new ArrayList<List<String>>(map.values());
    }

  • 0
    Y

    sort the map is pretty smart


  • 0
    M

    Did not expect that either... thanks.


  • 0

    Sorting the map buckets helped. Reduced by 10ms on an average (tried 4-5 times)


  • 0
    R

    Interesting discussion does anyone know why sorting buckets is faster ?


  • 32
    C

    Arrays.sort(strs) is not necessary since the question didn't ask you to return list of String that is in lexicographical order. If you remove this line, your result will be 99% of submission :)


  • 0
    S

    I agree. I removed it and ran it. It was accepted and much faster.


  • 5
    L

    I don't understand why you sort the final List, the problem doesn't ask for a sorted result.


  • 3
    F

    I have the similar idea as yours. But the hash table stores unique_str -> index_of_the_sub_list, rather than unique_str -> the_sub_list, which improves the speed a little bit.

    public class Solution {
        public List<List<String>> groupAnagrams(String[] strs) {
            List<List<String>> res = new ArrayList<>();
            if (strs == null || strs.length == 0) {
                return res;
            }
            
            Map<String, Integer> map = new HashMap<>(); // String to index in res
            for (String s: strs) {
                char[] c = s.toCharArray();
                Arrays.sort(c);
                String unique = new String(c);
                Integer idx = map.get(unique);
                
                if (idx == null) {
                    map.put(unique, map.size());
                    List<String> anotherRow = new ArrayList<>();
                    anotherRow.add(s);
                    res.add(anotherRow);
                } else {
                    res.get(idx).add(s);
                }
            }
            return res;
        }
    }
    

  • 0
    B

    @fyears thanks for your idea. At first I came up similar solutions as above (without unnecessary sorting of course), but it was taking too much time, like ~100ms. Didn't know what else could help, but using this indexing magic is indeed much faster. (Probably it takes a while to copy the results at the and with map.values).


  • 0

    can anyone comment on the time complexity of this code .
    Thanks


  • 2
    B

    @r.gupta8493gmail.com I think it's gonna be O(n * slogs). n is the number of string in strs array and s is the maximum length of string in the strs array. BTW, Arrays.sort(strs) is not needed.


  • 1
    W

    Nice solution, but why to sort strs?


  • 0

    Can anybody explain why sort the answer at last?


  • 0
    R

    really brilliant solution! nice work!


  • 0
    L

    @CodingRabbit yeh seems we have no reason to sort it at all.


  • 0

    can anyone explain the difference between Object.toString() and String.valueOf(Object)? Because I try to use cs.toString() to transform the sorted charArray to String, but the result shows like follows:
    [["ate"],["eat"],["nat"],["tan"],["bat"],["tea"]]

    but when I use String.valueOf(), the result is correct, I don't understand the different between these two methods


Log in to reply
 

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