very very good bit manipulation method which deserves a upvote.
However as @lzb700m mentioned, the time complexity is O(2^n * n) for your method.
2^n for the outer loop and n for the inner loop. Good, good, keep going.
def generateAbbreviations(self, word):
:type word: str
#taking care of the cache
if not cache[len(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
I guess one number cannot followed by another number unless the number counts exceeds 10. The number of counts may stand for the number of letters which are replaced by such a number. ie. when the number comes to 4, the word "under" has only two abbreviations -- 4r and u4. You may not consider 41 or 14 as an abbreviation. (May not be appropriate plz correct me if I'm wrong.)
Just consider it as a game of permutation and combination.