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.
"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)"23" ("ab" turned into "2" and "cde" turned into "3") is invalid as the substrings chosen are adjacent."22de" ("ab" turned into "2" and "bc" turned into "2") is invalid as the substring chosen overlap.Given a string word, return a list of all the possible generalized abbreviations of word. Return the answer in any order.
Example 1:
Input: word = "word" Output: ["4","3d","2r1","2rd","1o2","1o1d","1or1","1ord","w3","w2d","w1r1","w1rd","wo2","wo1d","wor1","word"]
Example 2:
Input: word = "a" Output: ["1","a"]
Constraints:
1 <= word.length <= 15word consists of only lowercase English letters.Problem Overview: Given a word, generate every possible generalized abbreviation. You can replace any consecutive substring with its length (for example, word → w2d, 1o1d, 4). The task is to enumerate all valid combinations while maintaining the correct abbreviation counts.
Approach 1: DFS Backtracking (Time: O(n * 2^n), Space: O(n))
This approach explores all abbreviation choices using backtracking. At each character you have two decisions: abbreviate it (increase a running count of skipped characters) or keep the character in the output string. When you choose to keep the character, you first append any accumulated count, then append the character itself. The recursion continues until the end of the word, where any remaining count is flushed to the result. This works because each character contributes a binary decision (abbreviate or keep), producing 2^n combinations, while each generated string requires up to O(n) work to build.
The key insight is separating the abbreviation count from the actual string construction. Instead of inserting numbers repeatedly, you carry a running counter and only append it when needed. This keeps the recursion clean and avoids generating invalid formats like consecutive numbers. Backtracking is the most intuitive solution for interviews and clearly demonstrates control over recursion and state management.
Approach 2: Binary Enumeration with Bitmask (Time: O(n * 2^n), Space: O(n))
This method treats the problem as a bit manipulation exercise. For a word of length n, every abbreviation corresponds to a binary mask from 0 to (1 << n) - 1. A bit value of 1 means the character at that index is abbreviated, while 0 means the character is kept. You iterate through each mask and build the abbreviation by counting consecutive 1 bits and writing the count when a 0 appears.
The advantage of this approach is its simplicity: the entire search space is generated through iteration rather than recursion. Each mask represents one decision pattern, and you convert it into a valid abbreviation by scanning the word once. The complexity remains O(n * 2^n) because there are 2^n masks and building each abbreviation requires scanning n characters. This approach is common when practicing enumeration problems involving string transformations.
Recommended for interviews: DFS backtracking is usually the expected explanation because it clearly models the decision process and demonstrates recursion skills. The bitmask enumeration approach is equally efficient and shows strong understanding of combinatorial generation using binary states. Mentioning both signals deeper algorithmic intuition.
We design a function dfs(i), which returns all possible abbreviations for the string word[i:].
The execution logic of the function dfs(i) is as follows:
If i geq n, it means that the string word has been processed, and we directly return a list composed of an empty string.
Otherwise, we can choose to keep word[i], and then add word[i] to the front of each string in the list returned by dfs(i + 1), and add the obtained result to the answer.
We can also choose to delete word[i] and some characters after it. Suppose we delete word[i..j), then the j th character is not deleted, and then add j - i to the front of each string in the list returned by dfs(j + 1), and add the obtained result to the answer.
Finally, we call dfs(0) in the main function.
The time complexity is O(n times 2^n), and the space complexity is O(n). Where n is the length of the string word.
Python
Java
C++
Go
TypeScript
Since the length of the string word does not exceed 15, we can use the method of binary enumeration to enumerate all abbreviations. We use a binary number i of length n to represent an abbreviation, where 0 represents keeping the corresponding character, and 1 represents deleting the corresponding character. We enumerate all i in the range of [0, 2^n), convert it into the corresponding abbreviation, and add it to the answer list.
The time complexity is O(n times 2^n), and the space complexity is O(n). Where n is the length of the string word.
| Approach | Complexity |
|---|---|
| DFS | — |
| Binary Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS Backtracking | O(n * 2^n) | O(n) | Best for interviews and recursive enumeration problems |
| Binary Enumeration (Bitmask) | O(n * 2^n) | O(n) | Useful when practicing bit manipulation or iterative generation |
Leetcode 320. Generalized Abbreviation. 中文 • Alina L • 2,098 views views
Watch 9 more video solutions →Practice Generalized Abbreviation with our built-in code editor and test cases.
Practice on FleetCode