Given an array of strings, group anagrams together.

For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],

Return:

[

  ["ate", "eat","tea"],

  ["nat","tan"],

  ["bat"]

]

Note: All inputs will be in lower-case.

public class Solution {

    public List<List<String>> groupAnagrams(String[] strs) {

        if(strs==null || strs.length==0){

            return null;

        }

        List<List<String>> resList=new ArrayList<List<String>>();

        Map<String, List<String>> map=new HashMap<String, List<String>>();

        for(int i=0; i<strs.length; i++){

            String str=strs[i];

            char[] chars=str.toCharArray();

            Arrays.sort(chars);

            String key=new String(chars);

            if(map.containsKey(key)){

                List<String> strList=map.get(key);

                strList.add(str);

                map.put(key,strList);

            }

            else{

                List<String> strList=new ArrayList<String>();

                strList.add(str);

                map.put(key, strList);

            }

        }

        for(String key : map.keySet()){

            resList.add(map.get(key));

        }

        return resList;

    }

}

class Solution {

    public List<List<String>> groupAnagrams(String[] strs) {

        List<List<String>> resList = new ArrayList<List<String>>();

        if(strs == null || strs.length == 0){

            return resList;

        }

        Map<Character, Integer> charMap = new HashMap<>();

        Map<Map<Character, Integer>, List<String>> strMap = new HashMap<>();

        for(String str : strs){

            Map<Character, Integer> key = generateCharMap(str);

            //The reason we can use containsKey here is because the key implements equals function

            if(strMap.containsKey(key)){

                List<String> list = strMap.get(key);

                list.add(str);

                strMap.put(key, list);

            }

            else{

                List<String> list = new ArrayList<>();

                list.add (str);

                strMap.put(key, list);

            }

        }

        for(Map<Character, Integer> key : strMap.keySet()){

            resList.add(strMap.get(key));

        }

        return resList;

    }

    private Map<Character, Integer> generateCharMap(String str){

        Map<Character, Integer> map = new HashMap<>();

        for(char c : str.toCharArray()){

            map.put(c, map.getOrDefault(c,0)+1);

        }

        return map;

    }

}