# 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]:
if suffix[0].isalpha():

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)