LeetCode 320: Generalized Abbreviation

Problem Restatement

We are given a lowercase string word.

Return all possible generalized abbreviations of word.

A generalized abbreviation replaces any number of non-overlapping and non-adjacent substrings with their lengths. For example, "abcde" can become "a3e", "1bcd1", "5", or "abcde". The input length is at most 15, and the answer can be returned in any order.

Input and Output

Function shape:

def generateAbbreviations(word: str) -> list[str]:
    ...

Examples

Example 1:

word = "word"

Possible output:

[
    "4",
    "3d",
    "2r1",
    "2rd",
    "1o2",
    "1o1d",
    "1or1",
    "1ord",
    "w3",
    "w2d",
    "w1r1",
    "w1rd",
    "wo2",
    "wo1d",
    "wor1",
    "word",
]

Example 2:

word = "a"

Output:

["1", "a"]

For one character, we either abbreviate it as 1 or keep it as "a".

First Thought: Choose for Every Character

For each character, we have two choices:

1. Keep the character.
2. Abbreviate the character.

For example:

word = "abc"

One choice pattern is:

keep a, abbreviate b, keep c

This gives:

"a1c"

Another pattern:

abbreviate a, abbreviate b, abbreviate c

This gives:

"3"

Adjacent abbreviated characters should be merged into one number. So "111" should become "3".

That means we should not append "1" immediately every time we abbreviate a character. Instead, keep a running count of abbreviated characters.

Key Insight

Use backtracking with three pieces of state:

At every character, choose:

1. Abbreviate it: increase count.
2. Keep it: first flush count into path, then append the character.

At the end, flush any remaining count and save the abbreviation.

Algorithm

Define:

backtrack(index, path, count)

If index == len(word):

1. If count > 0, append str(count).
2. Join path.
3. Add the result to answer.

Otherwise, at word[index]:

Choice 1: abbreviate this character.

backtrack(index + 1, path, count + 1)

Choice 2: keep this character.

1. If count > 0, append str(count).
2. Append word[index].
3. Recurse with count = 0.
4. Undo appended parts after recursion.

Correctness

For every character, the algorithm makes exactly two choices: abbreviate it or keep it.

Therefore, every possible keep-or-abbreviate pattern is explored.

The count variable records a run of consecutive abbreviated characters. When a kept character appears, the algorithm writes the count before writing that character. At the end of the word, it also writes any remaining count. Thus each generated string uses the proper numeric abbreviation for every maximal run of abbreviated characters.

Every generated abbreviation corresponds to one unique choice pattern over the characters of word.

Every valid generalized abbreviation can also be described by choosing which characters are abbreviated and which are kept. The algorithm explores that exact choice pattern and produces the abbreviation.

Therefore, the algorithm returns all and only valid generalized abbreviations.

Complexity

Let n = len(word).

The output itself contains 2^n strings.

Implementation

class Solution:
    def generateAbbreviations(self, word: str) -> list[str]:
        answer = []
        n = len(word)

        def backtrack(index: int, path: list[str], count: int) -> None:
            if index == n:
                original_len = len(path)

                if count > 0:
                    path.append(str(count))

                answer.append("".join(path))

                while len(path) > original_len:
                    path.pop()

                return

            backtrack(index + 1, path, count + 1)

            original_len = len(path)

            if count > 0:
                path.append(str(count))

            path.append(word[index])

            backtrack(index + 1, path, 0)

            while len(path) > original_len:
                path.pop()

        backtrack(0, [], 0)

        return answer

Code Explanation

We store all generated abbreviations in:

answer = []

The recursive function is:

def backtrack(index: int, path: list[str], count: int) -> None:

index tells us which character we are deciding.

path stores already written pieces.

count stores abbreviated characters that have not yet been written as a number.

When we reach the end:

if index == n:

we flush count if needed.

if count > 0:
    path.append(str(count))

Then we join the path.

answer.append("".join(path))

The first branch abbreviates the current character.

backtrack(index + 1, path, count + 1)

No string piece is added yet. We only increase the pending abbreviation count.

The second branch keeps the current character.

if count > 0:
    path.append(str(count))

path.append(word[index])

If there is a pending count, it must be written before the kept character.

Then recurse with count = 0.

backtrack(index + 1, path, 0)

After recursion, restore path so the next branch starts cleanly.

while len(path) > original_len:
    path.pop()

Bit Mask Implementation

Because word.length <= 15, we can also enumerate all bit masks.

A 1 bit means abbreviate the character.

A 0 bit means keep the character.

class Solution:
    def generateAbbreviations(self, word: str) -> list[str]:
        n = len(word)
        answer = []

        for mask in range(1 << n):
            parts = []
            count = 0

            for i in range(n):
                if mask & (1 << i):
                    count += 1
                else:
                    if count > 0:
                        parts.append(str(count))
                        count = 0

                    parts.append(word[i])

            if count > 0:
                parts.append(str(count))

            answer.append("".join(parts))

        return answer

This is compact and follows the same keep-or-abbreviate idea.

Testing

def normalize(values):
    return sorted(values)

def run_tests():
    s = Solution()

    assert normalize(s.generateAbbreviations("a")) == normalize([
        "1",
        "a",
    ])

    assert normalize(s.generateAbbreviations("ab")) == normalize([
        "2",
        "1b",
        "a1",
        "ab",
    ])

    assert normalize(s.generateAbbreviations("word")) == normalize([
        "4",
        "3d",
        "2r1",
        "2rd",
        "1o2",
        "1o1d",
        "1or1",
        "1ord",
        "w3",
        "w2d",
        "w1r1",
        "w1rd",
        "wo2",
        "wo1d",
        "wor1",
        "word",
    ])

    assert len(s.generateAbbreviations("abc")) == 8
    assert len(s.generateAbbreviations("abcd")) == 16

    print("all tests passed")

run_tests()

Test meaning: