Question

Write a function to generate the generalized abbreviations of a word.

Note: The order of the output does not matter.

Example:

Input: "word"
Output:
["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

DP Solution

class Solution(object):
    def generateAbbreviations(self, word):
        """
        :type word: str
        :rtype: List[str]
        """
        if len(word) == 0:
            return [""]

        dp = [[]] * (len(word) - 1)
        dp.append(["1", word[-1]])

        for idx in range(len(word) - 2, -1, -1):
            suffixes = set()
            for l in range(1, len(word) - idx):
                for suffix in dp[idx + l]:
                    suffixes.add(word[idx:idx+l] + suffix)
                    if suffix[0].isalpha():
                        suffixes.add(str(l) + suffix)

            suffixes.add(str(len(word) - idx))
            dp[idx] = list(suffixes)

        return dp[0]

Backtracking Solution

class Solution(object):
    def generateAbbreviations(self, word):
        """
        :type word: str
        :rtype: List[str]
        """
        if len(word) == 0:
            return [""]
        res = []

        self.backtracking(word, res, "", 0, 0)
        return res

    def backtracking(self, word, res, partial, count, idx):
        if idx == len(word):
            if count == 0:
                res.append(partial)
            else:
                res.append(partial + str(count))
        else:
            if count != 0:
                self.backtracking(word, res, partial + str(count) + word[idx], 0, idx + 1)
            else:
                self.backtracking(word, res, partial + word[idx], 0, idx + 1)
            self.backtracking(word, res, partial, count + 1, idx + 1)