Generalized Abbreviation — LeetCode 320 Python Solution

The problem

A word's generalized abbreviation can be constructed by taking any number of non-overlapping and non-adjacent substrings and replacing them with their respective lengths. For example, "abcde" can be abbreviated into: "a3e" ("bcd" turned into "3") "1bcd1" ("a" and "e" both turned into "1") "5" ("abcde" turned into "5") "abcde" (no substrings replaced) However, these abbreviations are invalid: "23" ("ab" turned into "2" and "cde" turned into "3") is invalid as the substrings chosen are adjacent.

Example

Input

word = "word"

Output

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

Python solution

class Solution:
    def generateAbbreviations(self, word: str) -> List[str]:
        def dfs(i: int) -> List[str]:
            if i >= n:
                return [""]
            ans = [word[i] + s for s in dfs(i + 1)]
            for j in range(i + 1, n + 1):
                for s in dfs(j + 1):
                    ans.append(str(j - i) + (word[j] if j < n else "") + s)
            return ans

        n = len(word)
        return dfs(0)

Complexity

Pattern: Backtracking

Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 320. Generalized Abbreviation is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Backtracking.

The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.

Related problems