# Python solution with detailed explanation

• Solution

Generalized Abbreviation https://leetcode.com/problems/generalized-abbreviation/

Method1: Backtracking

``````class Solution(object):
def helper(self, word, so_far, i, so_far_len, N):
if so_far_len == N:
self.result.append("".join(so_far))
return

candidates = [word[i]]
if len(so_far) == 0 or so_far[-1].isdigit() == False:
for x in range(1, N+1):
if so_far_len + x <= N:
candidates.append(x)

for c in candidates:
c_str = str(c)
so_far.append(c_str)
if c_str.isalpha() == False:
self.helper(word, so_far, i+c, so_far_len+c, N)
else:
self.helper(word, so_far, i+1, so_far_len+1, N)
so_far.pop()
return

def generateAbbreviations(self, word):
"""
:type word: str
:rtype: List[str]
"""
self.result = []
self.helper(word, [], 0, 0, len(word))
self.result.reverse()
return self.result
``````

Method2: Subset Based Solution

• How many valid abbreviations can there be? Each word may be included or not included and replaced by 1. Therefore we have 2^N possible abbreviations.
• The code for this method is straight-forward after this amazing insight! Either select the word and add to so_far, otherwise do not select and add 1.
• At process solution step, process the solution to compress all the 1s.
``````class Solution(object):
def compress(self, so_far):
csofar, i = [], 0
while i < len(so_far):
if so_far[i].isalpha():
csofar.append(so_far[i])
i += 1
else:
num = 0
while i < len(so_far) and so_far[i].isdigit():
num += 1
i += 1
csofar.append(str(num))
return "".join(csofar)

def helper(self, i, word, so_far, result):
if i == len(word):
result.append(self.compress(so_far))
else:
so_far.append(word[i])
self.helper(i+1, word, so_far, result)
so_far.pop()
so_far.append("1")
self.helper(i+1, word, so_far, result)
so_far.pop()
return

def generateAbbreviations(self, word):
"""
:type word: str
:rtype: List[str]
"""
result = []
self.helper(0, word, [], result)
return result
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.