JAVA 2 HashMaps + Sorting + Hashcode solution


  • 0
    F

    I used two hashmaps:

    1. To store the mapping of string index i of strs[i] to the hashcode of sorted strs[i]
    2. To store the mapping of all unique hashcodes to List of strings whose sorted version has the same hash code.

    Code below should be self explanatory. It took 34ms.

    class Solution {
    
        public List<List<String>> groupAnagrams(String[] strs) 
        {
            //Stores the mapping of index of any string strs[i] to hash code of sorted strs[i]
            HashMap<Integer,Integer> h = new HashMap<>();
            
            //Stores the the mapping of hashcode of of the above sorted strs[i] to anagrams of strs[i] avaliable in strs
            HashMap<Integer,List<String>> m = new HashMap<>();
            
            //Stores the final answer
            List<List<String>> ans = new LinkedList<>();
            
            //Checking for base conditions
            if((strs==null)||(strs.length<1))
            {
                return ans;
            }
            
            int i=0;
            int l = strs.length;
            
            //For each string in strs
            for(i=0;i<l;i++)
            {
                //Converting to char array for easier sorting of strs[i]
                char[] arr= strs[i].toCharArray();
                Arrays.sort(arr);
                String s = new String(arr);
                
                //Generating hashcode of sorted strs[i]
                Integer code = s.hashCode();
                
                //Mapping of index of string to hash code of sorted strs[i]
                h.put(i,code);
                
                //If no element has been seen wrt to the given hashcode
                if(m.get(code)==null)
                {
                    //Form a new linked list
                    List<String> lst = new LinkedList<String>();
                    //Add the string strs[i] to this list
                    lst.add(strs[i]);
                    //Put the list in the map
                    m.put(code,lst);
                }
                else
                {
                    //Get the existing list of strings
                    List<String> nlst = m.get(code);
                    //Add the current string to the list
                    nlst.add(strs[i]);
                    //Map the hash code to this updated list
                    m.put(code,nlst);
                }
            }
            
            //For each entry in hashmap
            for(Map.Entry<Integer,List<String>> iter: m.entrySet())
            {
                //Get the linked list corresponding to a particular hashcode
                List<String> slst = (LinkedList<String>)iter.getValue();
                //Add it to the final answer
                ans.add(slst);
            }
            //Return final answer
            return ans;
        }
    }
    

Log in to reply
 

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