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 non-overlapping and non-adjacent 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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

from typing import List

class Solution:
    def generateAbbreviations(self, word: str) -> List[str]:
        result = []

        def helper(start, current, count):
            if start == len(word):
                # If there is a pending count, append it to the current abbreviation
                if count > 0:
                    current += str(count)
                result.append(current)
                return

            # Abbreviate the current character by incrementing the count
            helper(start + 1, current, count + 1)

            # Keep the current character and append any pending count to the current abbreviation
            if count > 0:
                current += str(count)
            helper(start + 1, current + word[start], 0)

        # Start the recursion from the beginning of the word
        helper(0, "", 0)
        return result

Problem Size: 4

“word”

f(g) = f(g-x)

Reduce the problem size by some unit (1, 2, half, constant factor)

recurse(n-x)

[“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

1. 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

1. Define the Interface Input: String Output: Array of strings

2. Define the Term Generalized Abbreviation

3. 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)
   • Non-overlapping substrings

Observations

- If the length is 4, we need to replace 1, 2, 3 and 4

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

5. Classify the Problem

   • Permutation
   • Combination
   • Subset - Similar

6. 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

7. How do we generate these abbreviations?

   • If you don’t know, how can you do it by hand? Use pen and paper.

8. 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

9. Unit of Work Choices - Pick a letter from the given input - You can use an index from 0 to size-1 - 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’

10. How many times do we need to make the recursive call in the code?

Time: O( ) Space: O( )

Key Takeaways

=end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

def backtrack(word, index, combination, count, output)
#     base case
    if index == word.size
        if count != 0
            combination.append(count)
        end
        output.append(combination.join)
    else
        backtrack(word, index+1, combination, count+1, output)

  #     Add the digit
        if count != 0
            combination.append(count)
        end

#       Unit of work
#       Add the letter to the partial combination = ['w', 'o', 'r', 'd']
        combination.append(word[index])
        
        backtrack(word, index+1, combination, 0, output)        
    end
    combination.pop
end

# @param {String} word
# @return {String[]}
def generate_abbreviations(word)
    output = []
    combination = []
    count = 0
    backtrack(word, 0 , combination, count, output)
    return output
end