# Both Recursive and Iterative solution, clean code

• 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)``````

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