Problem statement

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

Solution

Backtracking problem, where on each step we can take two decisions: keep it as letter, or increase last numberby $1$. We need to dfs(index, current) function, where index is current index and current is abbreviation in list form, constructed so far.

Complexity

There will be exactly $2^n$ different abbreviations, so time and space complexity is $O(2^n\cdot n)$

Code

class Solution:
    def generateAbbreviations(self, word):
        def dfs(index, current):
            if index == n:
                self.result.append("".join(current))
                return

            dfs(index + 1, current + [word[index]])

            if current and current[-1] < "a":
                last = current.pop()
                current.append(str(int(last)+1))
                dfs(index + 1, current)
                current[-1] = last
            else:
                dfs(index + 1, current + [str(1)])
        
        n = len(word)
        self.result = []
        dfs(0, [])
        return self.result