hardBacktrackingPure DSA~35 min
Generate Every Generalized Abbreviation of a Word
A generalized abbreviation replaces any set of non-overlapping substrings with their lengths. Generate every distinct abbreviation of a given word.
Problem
Given a string word, a generalized abbreviation replaces any number of non-adjacent, non-overlapping substrings with the count of characters replaced (adjacent replaced runs merge into one number). Return all distinct generalized abbreviations in any order.
Input
A string word.
Output
A list of all generalized abbreviations.
Constraints
- 0 <= word.length <= 15
- word consists of lowercase letters.
- There are exactly 2^word.length abbreviations.
Examples
Example 1
Input
word = "word"
Output
["4","3d","2r1","2rd","1o2","1o1d","1or1","1ord","w3","w2d","w1r1","w1rd","wo2","wo1d","wor1","word"]
Each character is either kept or abstracted into a count.
Example 2
Input
word = "a"
Output
["1","a"]
Keep the letter or abbreviate it as 1.