Python Backtracking Solutions with and without Cache


  • 1
    S

    It seems like with cache, we would save a lot of repeated work on some test cases.

    With cache (408 ms):

    class Solution(object):
        def __init__(self):
            self._cache = {}
        
        def generateAbbreviations(self, word):
            """
            :type word: str
            :rtype: List[str]
            """
            if not word:
                return [""]
            if word in self._cache:
                return self._cache[word]
            n = len(word)
            abbs = []
            for i in range(n, 0, -1):
                abbs.extend(str(i)+a for a in self.generateAbbreviations(word[i:]) if not a or not a[0].isdigit())
            abbs.extend(word[0]+a for a in self.generateAbbreviations(word[1:]))
            self._cache[word] = abbs
            return abbs
    

    Without cache (816 ms):

    class Solution(object):
        def generateAbbreviations(self, word):
            """
            :type word: str
            :rtype: List[str]
            """
            return self._helper(word)
        
        def _helper(self, word, prev_is_num=False):
            if not word:
                return [""]
            n, abbs = len(word), []
            if not prev_is_num:
                for i in range(n, 0, -1):
                    abbs.extend(str(i) + a for a in self._helper(word[i:], True))
            abbs.extend(word[0] + a for a in self._helper(word[1:]))
            return abbs

Log in to reply
 

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