Generalized Abbreviation

Problem: Generalized Abbreviation

We can use a breadth-first search style approach to solve the problem. We start from an empty string and try to add characters from the first one. Every time we can add the character or drop the letter by adding a number. When we are adding numbers, we need to check whether there's a number before to decide whether to do the accumulation.

Code in Python:

class Solution(object):
    def generateAbbreviations(self, word):
        """
        :type word: str
        :rtype: List[str]
        """
        nums = "0123456789"
        res = [""]
        for c in word:
            next = []
            for abbr in res:
                i, n, base, num = -1, len(abbr), 1, 0
                while -i <= n:
                    if abbr[i] in nums:
                        num += base * int(abbr[i])
                        base *= 10
                        i -= 1
                    else: break
                if num == 0: next += [abbr+"1", abbr+c]
                else: next += [abbr[:i+1]+str(1+num), abbr[:i+1]+str(num)+c]
            res = next
        return res