Generalized Abbreviation - Leetcode Solution

The Generalized Abbreviation problem on Leetcode can be solved using the backtracking approach.

The problem statement is as follows:

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

Example:

Input: "word" Output: [ "w4", "w3d", "w2r1", "w1o2", "w1o1d", "wo3", "wo2r1", "wo1r2", "wo1r1d", "w1or2", "w1o1r1", "word" ]

The generalized abbreviations of the word "word" are as follows:

w4, w3d, w2r1, w1o2, w1o1d, wo3, wo2r1, wo1r2, wo1r1d, w1or2, w1o1r1, word.

The first step is to create a function that will take the input string, its current position, and the current abbreviation as arguments.

The function will start with the current position and the current abbreviation as 0 and an empty string respectively.

The function will then create two recursive calls, one where the next character is abbreviated and one where the next character is kept in its original form.

If the current position is at the end of the string, the function will append the current abbreviation to the output list.

Here's the Python code for the solution:

class Solution:
    def generateAbbreviations(self, word: str) -> List[str]:
        def backtrack(word, i, cur, count, res):
            if i == len(word):
                if count > 0:
                    cur += str(count)
                res.append(cur)
            else:
                backtrack(word, i + 1, cur, count + 1, res)
                backtrack(word, i + 1, cur + (str(count) if count > 0 else '') + word[i], 0, res)
        
        res = []
        backtrack(word, 0, '', 0, res)
        return res

Time complexity: O(2^n) where n is the length of the input string. Space complexity: O(2^n) for the output list.

1