Share my Java solution using Map.


  • 0
    L

    A straightforward solution.

    1.Sort strs list.

    Since "inner list's elements must follow the lexicographic order", I sort the list first.

    2.Use a map. KEY would be a sorted string, and VALUE is the location of the "group" in the groups list.

    3.Iterate the strs list.
    Sort the strs item. If the map contains that sorted string, get the location of that anagram group from the map, add that string to that group.
    If the map doesn't contain that sorted string, populate a new map item and a group list.

        public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res = new ArrayList<List<String>>();
        Arrays.sort(strs);// you can add your sorting method here, but I use the util class for the simplicity of code
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        for(int i = 0; i < strs.length; ++i){
            String curr = sortAString(strs[i]);
            if(map.containsKey(curr)){
                int loc = map.get(curr);
                res.get(loc).add(strs[i]);
            }else{
                map.put(curr, res.size());
                List<String> newGroup = new ArrayList<String>();
                newGroup.add(strs[i]);
                res.add(newGroup);
            }
        }
        return res;
    }
    //bucket sort. 
    private String sortAString(String str){
        int[] bucket = new int[26];
        for(int i = 0; i < str.length(); ++i){
            ++bucket[str.charAt(i) - 'a'];
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < bucket.length; ++i){
            int num = bucket[i];
            while(num > 0){
                sb.append(i + 'a');
                --num;
            }
        }
        return sb.toString();
    }

Log in to reply
 

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