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

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

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

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