LeetCode 247: Strobogrammatic Number II

Problem Restatement

We are given an integer n.

Return all strobogrammatic numbers of length n.

A strobogrammatic number is a number that looks the same after being rotated 180 degrees. The answer may be returned in any order. The constraint is 1 <= n <= 14.

The valid rotated digit pairs are:

But there is one important rule: the outermost pair cannot be 0 and 0, because that would create a leading zero.

For example, "00" is not a valid length-2 number.

Input and Output

Example function shape:

def findStrobogrammatic(n: int) -> list[str]:
    ...

Examples

Example 1:

n = 2

The valid length-2 strobogrammatic numbers are:

["11", "69", "88", "96"]

The pair "00" is excluded because it has a leading zero.

Example 2:

n = 1

The valid length-1 strobogrammatic numbers are:

["0", "1", "8"]

Only 0, 1, and 8 can rotate into themselves.

Example 3:

n = 3

We can place a valid center digit first:

["0", "1", "8"]

Then wrap each one with valid outer pairs except "00".

Some results are:

["101", "609", "808", "906"]

First Thought

We could generate every length-n string made of digits and check whether it is strobogrammatic.

There are 10^n possible strings.

For n = 14, that is far too many.

We need to generate only valid strobogrammatic numbers.

Key Insight

A strobogrammatic number is built from mirrored digit pairs.

For example:

"69"

is valid because 6 rotates to 9.

A longer number can be built by putting a valid pair around a smaller strobogrammatic number.

For example:

"1" -> "609"

Here, we wrap "1" with 6 and 9.

So we can build numbers from the inside out.

Base cases:

Then for longer lengths, wrap each inner value with valid pairs.

The pair "00" is allowed only for inner layers, not for the outermost layer.

Algorithm

Define a helper function:

build(length, total_length)

It returns all strobogrammatic strings of size length.

Base cases:

if length == 0:
    return [""]

if length == 1:
    return ["0", "1", "8"]

Recursive step:

1. Generate all inner strings of length length - 2.
2. For each inner string, wrap it with valid pairs.
3. Skip "00" when length == total_length.
4. Return the result.

Correctness

The algorithm builds every result by placing valid rotated digit pairs around a smaller strobogrammatic string.

Each pair preserves the strobogrammatic property because the left digit rotates into the right digit and the right digit rotates into the left digit.

The base cases are correct:

[""]

represents the empty center for even lengths.

["0", "1", "8"]

represents all valid one-digit centers.

For any length greater than 1, every strobogrammatic number has an outer pair from the valid pair set. After removing that pair, the remaining middle part is also strobogrammatic.

The algorithm tries every valid outer pair for every valid inner string. It skips "00" only at the outermost level, which prevents leading-zero numbers while still allowing zeros inside the number.

Therefore, the algorithm returns exactly all valid strobogrammatic numbers of length n.

Complexity

Let R be the number of generated answers.

A loose upper bound for R is about 5^(n/2) because each mirrored layer has at most five pair choices.

Implementation

class Solution:
    def findStrobogrammatic(self, n: int) -> list[str]:
        pairs = [
            ("0", "0"),
            ("1", "1"),
            ("6", "9"),
            ("8", "8"),
            ("9", "6"),
        ]

        def build(length: int, total_length: int) -> list[str]:
            if length == 0:
                return [""]

            if length == 1:
                return ["0", "1", "8"]

            result = []

            for middle in build(length - 2, total_length):
                for left, right in pairs:
                    if length == total_length and left == "0":
                        continue

                    result.append(left + middle + right)

            return result

        return build(n, n)

Code Explanation

The pairs list stores every valid mirrored rotation:

pairs = [
    ("0", "0"),
    ("1", "1"),
    ("6", "9"),
    ("8", "8"),
    ("9", "6"),
]

The helper function builds valid strings of a target length:

def build(length: int, total_length: int) -> list[str]:

We keep total_length so we can detect the outermost layer.

For even-length centers, we return an empty string:

if length == 0:
    return [""]

For odd-length centers, we return the valid self-rotating digits:

if length == 1:
    return ["0", "1", "8"]

Then we build larger strings by wrapping smaller ones:

for middle in build(length - 2, total_length):

For each middle string, try every pair.

for left, right in pairs:

Skip leading zero at the outermost level:

if length == total_length and left == "0":
    continue

Then append the new string:

result.append(left + middle + right)

Finally, return all generated strings.

Testing

Since the answer may be returned in any order, compare sets.

def run_tests():
    s = Solution()

    assert set(s.findStrobogrammatic(1)) == {"0", "1", "8"}

    assert set(s.findStrobogrammatic(2)) == {
        "11",
        "69",
        "88",
        "96",
    }

    assert set(s.findStrobogrammatic(3)) == {
        "101",
        "111",
        "181",
        "609",
        "619",
        "689",
        "808",
        "818",
        "888",
        "906",
        "916",
        "986",
    }

    assert "00" not in set(s.findStrobogrammatic(2))
    assert "010" not in set(s.findStrobogrammatic(3))

    print("all tests passed")

run_tests()