MediumNo. 0320LeetCode Premium
Generalized Abbreviation — LeetCode 320 Python Solution
- Pattern
- Backtracking
- Topics
- Bit Manipulation, String, Backtracking
- Reading time
- 3 min
- Source
- leetcode.com
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
- Time
- O(n × 2n)
- Space · auxiliary
- O(n)
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
| No. | Problem | Difficulty |
|---|---|---|
| 0784 | Letter Case Permutation | Medium |
| 1239 | Maximum Length of a Concatenated String with Unique Characters | Medium |
| 0078 | Subsets | Medium |
| 0079 | Word Search | Medium |
| 0089 | Gray Code | Medium |
| 0090 | Subsets II | Medium |
Frequently asked questions
- How hard is LeetCode 320. Generalized Abbreviation?
LeetCode 320. Generalized Abbreviation is rated Medium on LeetCode.
- What is the time complexity of LeetCode 320. Generalized Abbreviation?
The Python solution on this page runs in O(n × 2n).
- What is the space complexity of LeetCode 320. Generalized Abbreviation?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 320. Generalized Abbreviation cover?
LeetCode 320. Generalized Abbreviation is tagged Bit Manipulation, String and Backtracking on LeetCode.
- Is LeetCode 320. Generalized Abbreviation a premium problem?
Yes. LeetCode 320. Generalized Abbreviation is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.