a b c d e f
1 b + recurse on rest
2 c + recurse on rest
3 d + recurse on rest
4 e + recurse on rest
5 f + recurse on rest
For the case of 1b + recurse(cdef), if recurse(cdef) returns "1d1f", then we just have to append "1b" to the head of that subsolution.
Duplicate is removed obviously as you can see: no two iterations shares the same headings.
Of course you also have to include solutions like "6" for "abcdef" but that can be handled as a trivial base case. Once that is handled, you can rest assured that there will be at least one letter in the other results. The loop iterate on this survivor letter's positin (i) and do the recursion as shown above.
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.