Python recursive, using a list to cache, slightly faster than a dict


  • 3
    C

    I played a little bit with speed, I report my result numbers here, hoping it might be useful to someone, or could inspire some answers that are a lot more insightful. Without cache my time was 570ms. with a dict cache, 390ms, with a list cache, 352ms. I guess there is large overhead for the list cache in the case, the difference might be more obvious for long strings.

    class Solution(object):
    
    def __init__(self):
        self.cache=[[]]
    
    def generateAbbreviations(self, word):
        """
        :type word: str
        :rtype: List[str]
        """
        #taking care of the cache
        if len(word)+1>len(self.cache):
            self.cache=[[]for _ in xrange(len(word)+1)]
        if self.cache[len(word)]:
            return self.cache[len(word)]
    
        #core solution
        result=[word]
        #length of first abbr
        for k in xrange(1, len(word)+1):
            #length before the first abbr
            for p in xrange(len(word)-k+1):
                pre=word[:p]+str(k)+(word[p+k] if p+k <len(word) else '')
                result.extend([pre+s for s in self.generateAbbreviations(word[p+k+1:])])
    
        # put in cache
        self.cache[len(word)]=result
    
        return result

  • 1
    I

    minor improvement:

    class Solution(object):
    
        def generateAbbreviations(self, word):
            """
            :type word: str
            :rtype: List[str]
            """
            #taking care of the cache
            cache=[0]*(len(word)+1)
            def search(wd):
                if not cache[len(wd)]:
                    #core solution
                    result=[wd]
                    #length of first abbr
                    for k in xrange(1, len(wd)+1):
                        #length before the first abbr
                        for p in xrange(len(wd)-k+1):
                            pre=wd[:p]+str(k)+(wd[p+k] if p+k <len(wd) else '')
                            result.extend([pre+s for s in search(wd[p+k+1:])])
                    # put in cache
                    cache[len(wd)]=result
                return cache[len(wd)]
            return search(word)
    

Log in to reply
 

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