Generalized Abbreviation
The problem requires us to generate all possible generalized abbreviations of a given word. A generalized abbreviation can be constructed by replacing any number of nonoverlapping and nonadjacent substrings with their respective lengths.
To tackle this problem, we can use recursion or iteration to try every possible abbreviation. Since every character can either be abbreviated or not, there are 2^n possible abbreviations where n is the length of the word.
Here’s the code snippet using recursion:


Problem Size: 4
“word”
f(g) = f(gx)
Reduce the problem size by some unit (1, 2, half, constant factor)
recurse(nx)
[“5”,“4e”,“3d1”,“3de”,“2c2”,“2c1e”,“2cd1”,“2cde”,“1b3”,“1b2e”,“1b1d1”,“1b1de”,“1bc2”, “1bc1e”,“1bcd1”,“1bcde”,“a4”,“a3e”,“a2d1”,“a2de”,“a1c2”,“a1c1e”,“a1cd1”,“a1cde”,“ab3”,“ab2e”,“ab1d1”,“ab1de”,“abc2”,“abc1e”,“abcd1”,“abcde”]
We need to use the previosly generated combination.
Problem Decomposition
 We have word with 4 letters, we can split the word into one letter on side and spit it by 2, 3, and 4. Either we can go from right to left or left to right.
Going from smaller to larger values is bottom up  tabular approach. n = 0 n = 1 n = 2 n = 3
Recursive Approach n = 3 n = 2 n = 1 n = 0
Define the Interface Input: String Output: Array of strings
Define the Term Generalized Abbreviation
Identify the Invariant Invariant: What remains the same in this problem.
 Each abbreviation has to be a subset of the combination
 Word does not change
 Length of the combination (track if we have a valid combination)
 Nonoverlapping substrings
Observations
 If the length is 4, we need to replace 1, 2, 3 and 4
Look for clues in the problem space
List of all possible Subsets  Recursion  What elements in this approach can be use in this problem?  Include/Exclude or Use a loop and make recursive calls within the loop?
Building Your Own Language
 Recursion
 Backtracking
Clues in the problem space can give you insight in the solution
Classify the Problem
 Permutation
 Combination
 Subset  Similar
How do we interleave number and letters to form the strings? Digits go from size of the input to 1 (n..1) Each digit goes into every possible slot in the string
How do we generate these abbreviations?
 If you don’t know, how can you do it by hand? Use pen and paper.
How do we know we have generated all the possible abbreviations? Base Case
 When the index is equal to length of the input
 Add the combination to the output
Unit of Work Choices  Pick a letter from the given input  You can use an index from 0 to size1  The child will get an index that is incremente by 1  Instead of picking a letter, add the digit for the skipped letter into the partial combination you are building. “word”
When do we do our UoW (before or after the recursive call) Before we make the recursive call, we will add the letter to the combination
Pick a letter or the digit
We will have two recursive calls in the code.
Explore
word
’’  Initial ‘w’  First level ‘wo’  Second level ‘wor’  Third level ‘word’  Leaf node
’’ ‘3d’
 How many times do we need to make the recursive call in the code?
Time: O( ) Space: O( )
Key Takeaways
=end

