Both Recursive and Iterative solution, clean code


  • 0

    Recursive solution

    class Solution(object):
        def generate(self, word, preIsDigit):
            if not word:
                return [[]]
    
            r = [[word[0]] + p for p in self.generate(word[1:], False)]
            if not preIsDigit:
                r += sum([[[str(i)] + p for p in self.generate(word[i:], True)] for i in xrange(1, len(word) + 1)], [])
            return r
    
        def generateAbbreviations(self, word):
            return map(''.join, self.generate(word, False))
    

    Recursive solution with cache

    class Solution(object):
        def cache(f):
            def method(obj, *args):
                key = '{}:{}'.format(*args)
    
                if not hasattr(obj, 'r'):
                    setattr(obj, 'r', {})
    
                if key not in obj.r:
                    obj.r[key] = f(obj, *args)
    
                return obj.r[key]
            return method
    
        @cache
        def generate(self, word, preIsDigit):
            if not word:
                return [[]]
    
            r = [[word[0]] + p for p in self.generate(word[1:], False)]
            if not preIsDigit:
                r += sum([[[str(i)] + p for p in self.generate(word[i:], True)] for i in xrange(1, len(word) + 1)], [])
            return r
    
        def generateAbbreviations(self, word):
            return map(''.join, self.generate(word, False))
    

    Iterative solution using queue

    class Solution(object):
        def generateAbbreviations(self, word):
            if not word:
                return ['']
    
            word = collections.deque(word)
            queue = collections.deque([[word.popleft()], [1]])
    
            while word:
                char = word.popleft()
    
                for _ in xrange(len(queue)):
                    node = queue.popleft()
                    queue += [node + [char]] + ([node[:-1] + [node[-1] + 1]] if isinstance(node[-1], int) else [node + [1]])
    
            return map(lambda r: ''.join(map(str, r)), queue)

Log in to reply
 

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