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

  • 0

    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++)
                //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++){
                        sb.append((char) ('a'+j));
                String hash = sb.toString();
                //Chech if an entry exists in hash table already, else add a new one
                    hm.put(hash,new LinkedList<String>());
                //Add this string to the list pointed by hash

Log in to reply

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