My AC code in Python is O(m*n) in time and O(log(m)*n) in space. Could you still improve it further?


  • 0
    C

    Instead of using sort, I used count sort since there are only 26 lower case letters. Therefore the time complexity is O(m) in ordering a string with average length of m. Then gives the hash value of the string with run-length code which costs O(log(m)) space for a single string.
    Any idea to further improve the code since this costs 1080ms where my c++ version only costs 264ms.

     class Solution:
            # @param strs, a list of strings
            # @return a list of strings
            def contSort(self,instr):
                cont=[0 for i in range(26)];
                for i in range(len(instr)):
                    cont[ord(instr[i])-ord('a')]=cont[ord(instr[i])-ord('a')]+1;
                hashval="";
                for i in range(26):
                    hashval+=chr(ord('a')+i)+str(cont[i]);
                return hashval
            def anagrams(self, strs):
                res=[];
                if len(strs)<1:
                    return res;
                mydict={};
                for i in strs:
                    hashval=self.contSort(i);
                    if hashval in mydict:
                        mydict[hashval].append(i);
                    else:
                        mydict[hashval]=[i];
                
                
                for i in mydict:
                    if len(mydict[i])>1:
                        for j in mydict[i]:
                            res.append(j)
                
                return res;

  • 1
    H

    counting sort function (contSort in your code) can return tuple of 26 integers (counts) since tuples can be used as keys to dictionaries.
    So you can just insert the following after the first loop in the contSort function

    return tuple(cont)
    

    After many other improvements following is the optimized version that runs in ~400ms.

    However if we use standard sorting, it runs in ~350ms. This is becuase words are short and standard sort runs faster in these cases.

        def contSort(self,instr):
            cont=[0] * 26;
            for s in instr:
                cont[ord(s)-97]+=1 #97 is the ASCII code for 'a'
            return tuple(cont)
    
        def anagrams(self, strs):
            d = collections.defaultdict(list)
            for s in strs:
                d[self.contSort(s)].append(s)     #comment this out if you want to try Regular sort
                #d[''.join(sorted(s))].append(s)  #use this if you want to try Regular sort
            
            result = list()
            for wkey,wordlist in d.iteritems():
                if len(wordlist)>1:
                    result+=wordlist
            return result
    

  • 0
    L
    This post is deleted!

  • 0
    C

    This is a run-length coding. Simply analysis of one letter cases: saying there is 3 A, AAA with hashvalue len(A3)=2, 10 As AAA...A with len(A10)=3, 100 AAA...A with len(A100)=4, where the length of hashvalue equals 2+log10(Num_of_letters_in_str). So the space complexity is O(log(m)).


  • 0
    J

    The array in the tuple is not compressed.


Log in to reply
 

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