O(M*N) solution . NO sort and NO costly prime multiplication.


  • 0
    M

    Sorting is O(M log M * N) , where M is the average length of each string. Also how feasible is prime number multiplication for large inputs. For strings of size 20 or 50 or 100??

    Here is a O(M*N) solution without sort and without costly prime multiplication. Most solutions use sort, my idea is to use a counter instead of sort. My hash construction is constant time and does not change with input size, O(26).

    public List<List<String>> groupAnagrams(String[] strs) {
            
            HashMap<String,List<String>> hm = new HashMap<String,List<String>>();
            
            for(int i=0; i<strs.length; i++){
                String eachString = strs[i];
                
                //only lower-case letters. so array of size 26 is enough
                int[] counter = new int[26];
                
                //Iterate the string and increment corresponding index
                //char - 'a' , so the index will be between 0 and 25
                for(int j=0; j<eachString.length(); j++)
                    counter[eachString.charAt(j)-'a']++;
                
                //Now iterate thorugh the counter array and construct the hash 
                //Eg: cat becomes 1a1c1t. caabbt becomes 2a2b1c1t
                StringBuilder sb = new StringBuilder("");
                for(int j=0; j<26; j++){
                    if(counter[j]>0){
                        sb.append(counter[j]);
                        sb.append((char) ('a'+j));
                    }
                }
                
                String hash = sb.toString();
                
                //Chech if an entry exists in hash table already, else add a new one
                if(!hm.containsKey(hash))
                    hm.put(hash,new LinkedList<String>());
                    
                //Add this string to the list pointed by hash
                hm.get(hash).add(eachString);
            }
    

Log in to reply
 

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