LeetCode 320: Generalized Abbreviation Solution in Python – A Step-by-Step Guide

What Is LeetCode 320: Generalized Abbreviation?

In LeetCode 320: Generalized Abbreviation, you’re given a string word, and your task is to return a list of all possible generalized abbreviations. An abbreviation replaces any number of consecutive letters with their count (e.g., "ab" → "2"), but you can’t have adjacent numbers (e.g., "1o1d" is valid, not "2rd2"). For "word", you’d get 16 variations, from "word" to "4". This problem tests your ability to generate combinations systematically, connecting to ideas in LeetCode 78: Subsets.

Problem Statement

• Input: A string word of lowercase English letters.
• Output: A list of strings—all possible generalized abbreviations.
• Rules:
• Replace 0 or more consecutive letters with their count.
• No adjacent numbers in the result.
• Order of results doesn’t matter.

Constraints

• 1 <= word.length <= 15
• word contains only lowercase English letters.

Examples

• Input: "word"
• Output: ["word","wor1","wo2","w3","1ord","1o2","1or1","2rd","2r1","3d","w1rd","w1r1","w2d","4"]
• Input: "a"
• Output: ["a","1"]
• Input: "ab"
• Output: ["ab","a1","1b","2"]

Understanding the Problem: Generating Abbreviations

To solve LeetCode 320: Generalized Abbreviation in Python, we need to produce every valid abbreviation of word, where each position can either keep its letter or contribute to a count of consecutive abbreviated letters. A naive approach—trying all possible replacements manually—gets messy fast. Instead, we’ll use:

• Best Solution (Bitmask): O(2^n) time, O(2^n) space—clean and efficient.
• Alternative Solution (Recursive): O(2^n) time, O(2^n) space—intuitive but verbose.

Let’s start with the bitmask solution, explained in a beginner-friendly way.

Best Solution: Bitmask Approach

Why This Is the Best Solution

The bitmask approach is the top choice for LeetCode 320 because it’s efficient—O(2^n) time, O(2^n) space—and uses binary numbers to systematically generate all combinations of kept/abbreviated letters in one pass. Each bit decides whether a letter is kept (0) or counted (1), and we merge counts afterward. It’s like flipping switches to spell out every possibility—smart and streamlined!

How It Works

Think of this as a binary word builder:

• Step 1: Generate Masks:
• For a word of length n, use numbers 0 to 2^n - 1.
• Each bit: 0 = keep letter, 1 = abbreviate.
• Step 2: Build Abbreviation:
• Traverse word with mask.
• Count consecutive 1s, append count or letter.
• Step 3: Collect Results:
• Store all valid abbreviations.
• Step 4: Why It Works:
• 2^n masks cover all possibilities.
• Post-processing ensures no adjacent numbers.

It’s like a binary abbreviation generator—fast and fun!

Step-by-Step Example

Example: word = "ab"

• Masks: 00 (0), 01 (1), 10 (2), 11 (3)
• Process:
• 00: Keep a, keep b → "ab"
• 01: Keep a, count b (1) → "a1"
• 10: Count a (1), keep b → "1b"
• 11: Count a-b (2) → "2"
• Result: ["ab", "a1", "1b", "2"]

Code with Detailed Line-by-Line Explanation

Copy codeclass Solution:
    def generateAbbreviations(self, word: str) -> List[str]:
        n = len(word)
        result = []

        # Generate all 2^n masks
        for mask in range(1 << n):
            abbr = []
            count = 0
            # Build abbreviation based on mask
            for i in range(n):
                if mask & (1 << i):  # Bit is 1, abbreviate
                    count += 1
                else:  # Bit is 0, keep letter
                    if count > 0:
                        abbr.append(str(count))
                        count = 0
                    abbr.append(word[i])
            # Append final count if any
            if count > 0:
                abbr.append(str(count))
            result.append(''.join(abbr))

        return result

• Line 3: Get word length.
• Line 5: Loop over 2^n masks (0 to 2^n - 1).
• Lines 7-17: For each mask:
• Track count of consecutive 1s.
• If 1, increment count; if 0, append count (if any) then letter.
• Lines 18-19: Handle trailing count.
• Line 20: Join and add to result.
• Time Complexity: O(2^n)—generate all combinations.
• Space Complexity: O(2^n)—store all results.

This is like a bit-driven word shortener—crisp and quick!

Alternative Solution: Recursive Approach

Why an Alternative Approach?

The recursive approach also runs in O(2^n) time, O(2^n) space, building abbreviations by deciding at each position whether to keep the letter or abbreviate it, recurring on the rest. It’s more intuitive for some, showing the decision tree explicitly, though it’s less concise. It’s like crafting abbreviations step-by-step—clear and thoughtful!

How It Works

Recurse through decisions:

• Step 1: At each position:
• Keep letter, recur on rest.
• Abbreviate (count increases), recur.
• Step 2: Base case:
• Empty string returns [""].
• Step 3: Combine results.

Step-by-Step Example

Example: word = "ab"

• Recurse:
• "ab": Keep a → "a" + rec("b"), Count 1 → "1" + rec("b")
• "b": Keep b → "b", Count 1 → "1"
• Combine:
• "a" + ["b", "1"] → ["ab", "a1"]
• "1" + ["b", "1"] → ["1b", "2"]
• Result: ["ab", "a1", "1b", "2"]

Code for Recursive Approach

Copy codeclass Solution:
    def generateAbbreviations(self, word: str) -> List[str]:
        def recurse(s, pos):
            if pos == len(s):
                return [""]

            # Keep current letter
            keep = [s[pos] + rest for rest in recurse(s, pos + 1)]
            # Abbreviate current letter
            abbr = []
            for i in range(1, len(s) - pos + 1):
                rest = recurse(s, pos + i)
                for r in rest:
                    abbr.append(str(i) + r)

            return keep + abbr

        return recurse(word, 0)

• Lines 3-13: Recursive function:
• Base case: empty string.
• Keep letter and recur.
• Try all abbreviation counts and recur.
• Line 15: Start recursion.
• Time Complexity: O(2^n)—exponential combinations.
• Space Complexity: O(2^n)—result storage.

It’s a recursive abbreviation explorer—detailed and direct!

Comparing the Two Solutions

• Bitmask (Best):
• Pros: O(2^n) time, O(2^n) space, single pass.
• Cons: Bit logic less intuitive.
• Recursive (Alternative):
• Pros: O(2^n) time, O(2^n) space, clear decision tree.
• Cons: More verbose, recursion overhead.

Bitmask wins for efficiency.

Additional Examples and Edge Cases

• "a": ["a", "1"].
• "abc": ["abc", "ab1", "a1c", "a2", "1bc", "1b1", "2c", "3"].
• "": [""] (if allowed, else adjust base case).

Both handle these well.

Complexity Breakdown

• Bitmask: Time O(2^n), Space O(2^n).
• Recursive: Time O(2^n), Space O(2^n).

Bitmask is slightly leaner.

Key Takeaways

• Bitmask: Binary power—efficient!
• Recursive: Stepwise build—educational!
• Python: Bit ops and lists shine—see [Python Basics](/python/basics).
• Combinations: Abbreviation fun unleashed.

Final Thoughts: Abbreviate Creatively

LeetCode 320: Generalized Abbreviation in Python is a combinatorial wordplay delight. The bitmask solution offers speed and elegance, while recursion provides a clear process. Want more string manipulation? Try LeetCode 78: Subsets or LeetCode 46: Permutations. Ready to abbreviate? Head to Solve LeetCode 320 on LeetCode (premium) and shorten that word today!