LeetCode 247 - Strobogrammatic Number II

The problem asks us to generate every strobogrammatic number of a given length n. A strobogrammatic number is a number that still appears valid after being rotated 180 degrees. Not every digit works under rotation.

leetcodemediumarraystringrecursion

LeetCode Problem 247

Difficulty: 🟡 Medium
Topics: Array, String, Recursion

Solution

Problem Understanding

The problem asks us to generate every strobogrammatic number of a given length n.

A strobogrammatic number is a number that still appears valid after being rotated 180 degrees. Not every digit works under rotation. Only the following digit mappings are valid:

Original Rotated
0 0
1 1
6 9
8 8
9 6

For example, "69" becomes "96" after rotation, which is still a valid number. Similarly, "88" remains "88".

The input is a single integer n, representing the exact length of the numbers we must generate. The output is a list of strings because some generated values may begin with zeros internally during recursion, and string manipulation is more natural for this problem.

The constraints are small enough that generating all valid combinations is feasible. Since n <= 14, the total number of valid strobogrammatic numbers is manageable. This strongly suggests a constructive generation approach rather than checking every possible number.

Several edge cases are important:

  • Numbers cannot have leading zeros unless the number itself has length 1. For example, "00" is invalid for n = 2.
  • Odd-length numbers must have a valid middle digit that maps to itself. Only 0, 1, and 8 satisfy this condition.
  • Even-length numbers do not have a center digit, so every position must be paired symmetrically.
  • Recursive generation can accidentally produce invalid outermost zeros if not handled carefully.

Approaches

Brute Force Approach

A brute-force solution would generate every number with exactly n digits and check whether each one is strobogrammatic.

To verify a number, we could scan from both ends toward the center and ensure that every digit pair belongs to the valid rotation mappings. For example, if the left digit is 6, the corresponding right digit must be 9.

This approach is correct because it exhaustively checks every candidate. However, it is extremely inefficient. There are 10^n possible numbers of length n, which becomes enormous even for moderate values of n. Since n can be as large as 14, brute force is completely impractical.

Optimal Recursive Construction

The key observation is that strobogrammatic numbers are highly structured.

Instead of generating every possible number and filtering valid ones, we can directly construct only valid strobogrammatic numbers.

A strobogrammatic number is built symmetrically from the outside inward. If we place a digit on the left side, the right side is automatically determined by the rotation mapping.

For example:

  • If we place 6 on the left, we must place 9 on the right.
  • If we place 1 on the left, we must place 1 on the right.

This naturally leads to recursion:

  • Build smaller strobogrammatic numbers first.
  • Surround them with valid digit pairs.
  • Continue until the desired length is reached.

This avoids generating invalid candidates entirely.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(10^n × n) O(n) Generates every n-digit number and validates each
Optimal O(5^(n/2)) O(5^(n/2)) Constructs only valid strobogrammatic numbers recursively

Algorithm Walkthrough

Optimal Recursive Algorithm

  1. Define all valid strobogrammatic digit pairs.

We store the following pairs:

('0', '0')
('1', '1')
('6', '9')
('8', '8')
('9', '6')

These represent the only valid outer digit combinations. 2. Create a recursive helper function.

The helper function generates all strobogrammatic numbers of length currentLength.

We also keep track of the original target length so we can avoid leading zeros in the outermost layer. 3. Define the base cases.

If currentLength == 0, return [""].

This represents an empty center and allows recursive expansion outward.

If currentLength == 1, return ["0", "1", "8"].

These are the only digits that remain valid when rotated individually. 4. Recursively generate smaller strobogrammatic numbers.

We call the helper on currentLength - 2.

This generates all valid inner sections. 5. Expand each smaller result using valid pairs.

For every inner string:

  • Add "0" and "0" around it
  • Add "1" and "1" around it
  • Add "6" and "9" around it
  • Add "8" and "8" around it
  • Add "9" and "6" around it
  1. Prevent leading zeros.

When constructing the outermost layer, we must not place "0" at the front.

We detect this using:

if currentLength != originalLength

Inner recursive layers are allowed to contain zeros because they are not leading digits in the final result. 7. Return the constructed list.

After processing all inner strings and all valid pairs, the helper returns every valid strobogrammatic number for that length.

Why it works

The algorithm works because every strobogrammatic number must satisfy rotational symmetry. Each outer digit uniquely determines its mirrored counterpart. By recursively building the inner portion first and then surrounding it with valid digit pairs, the algorithm guarantees that every generated number is valid. Since every possible valid pair is explored at every level, no valid strobogrammatic number is missed.

Python Solution

from typing import List

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

        def build(current_length: int, target_length: int) -> List[str]:
            if current_length == 0:
                return [""]

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

            inner_numbers = build(current_length - 2, target_length)

            result = []

            for middle in inner_numbers:
                for left, right in pairs:
                    if current_length == target_length and left == '0':
                        continue

                    result.append(left + middle + right)

            return result

        return build(n, n)

The implementation starts by defining all valid strobogrammatic digit pairs. These pairs encode the rotational symmetry rules directly.

The recursive build function generates all valid strobogrammatic numbers for a given length. The parameter current_length represents the size currently being constructed, while target_length preserves the original requested size.

The base case for length 0 returns an empty string, which acts as a neutral center during recursive expansion. The base case for length 1 returns the only valid self-rotating digits.

For larger lengths, the function recursively generates all smaller valid inner strings. Each inner string is then wrapped with every valid digit pair.

The condition preventing leading zeros is crucial. We only skip the ('0', '0') pair when constructing the outermost layer. Inner layers may still contain zeros safely.

Finally, the function returns all constructed strings.

Go Solution

func findStrobogrammatic(n int) []string {
	pairs := [][]string{
		{"0", "0"},
		{"1", "1"},
		{"6", "9"},
		{"8", "8"},
		{"9", "6"},
	}

	var build func(int, int) []string

	build = func(currentLength int, targetLength int) []string {
		if currentLength == 0 {
			return []string{""}
		}

		if currentLength == 1 {
			return []string{"0", "1", "8"}
		}

		innerNumbers := build(currentLength-2, targetLength)

		result := []string{}

		for _, middle := range innerNumbers {
			for _, pair := range pairs {
				left := pair[0]
				right := pair[1]

				if currentLength == targetLength && left == "0" {
					continue
				}

				result = append(result, left+middle+right)
			}
		}

		return result
	}

	return build(n, n)
}

The Go solution follows the same recursive structure as the Python implementation. Slices are used to store generated strings dynamically.

One notable difference is that Go requires explicit function variable declarations for recursive anonymous functions. The build function is declared first and assigned afterward.

Go strings are immutable, just like Python strings, so concatenation creates new strings safely.

No integer overflow concerns exist because the algorithm operates entirely on strings rather than numeric conversions.

Worked Examples

Example 1

Input: n = 2

We call:

build(2, 2)

The recursive call becomes:

build(0, 2)

Since currentLength == 0, return:

[""]

Now expand using all valid pairs except leading zero.

Inner String Pair Result
"" ("1","1") "11"
"" ("6","9") "69"
"" ("8","8") "88"
"" ("9","6") "96"

We skip:

("0","0")

because it would create "00".

Final output:

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

Example 2

Input: n = 1

We call:

build(1, 1)

Since currentLength == 1, directly return:

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

Final output:

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

Additional Example

Input: n = 3

Start with:

build(3, 3)

Recursive call:

build(1, 3)

Base case returns:

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

Now expand each center digit.

Center Pair Constructed Number
"0" ("1","1") "101"
"0" ("6","9") "609"
"0" ("8","8") "808"
"0" ("9","6") "906"
"1" ("1","1") "111"
"1" ("6","9") "619"
"1" ("8","8") "818"
"1" ("9","6") "916"
"8" ("1","1") "181"
"8" ("6","9") "689"
"8" ("8","8") "888"
"8" ("9","6") "986"

Final output contains all 12 valid numbers.

Complexity Analysis

Measure Complexity Explanation
Time O(5^(n/2)) Each recursive layer branches into at most 5 valid digit pairs
Space O(5^(n/2)) Required to store all generated strobogrammatic numbers

The recursion depth is at most n / 2, since each step fills two positions. At every level, there are at most 5 branching choices. Therefore, the total number of generated strings is proportional to 5^(n/2).

The space complexity is dominated by the output itself, since all valid strobogrammatic numbers must be stored and returned.

Test Cases

from typing import List

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

        def build(current_length: int, target_length: int) -> List[str]:
            if current_length == 0:
                return [""]

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

            inner_numbers = build(current_length - 2, target_length)

            result = []

            for middle in inner_numbers:
                for left, right in pairs:
                    if current_length == target_length and left == '0':
                        continue

                    result.append(left + middle + right)

            return result

        return build(n, n)

solution = Solution()

# Example case for n = 1
assert sorted(solution.findStrobogrammatic(1)) == ["0", "1", "8"]

# Example case for n = 2
assert sorted(solution.findStrobogrammatic(2)) == ["11", "69", "88", "96"]

# Small odd length
assert sorted(solution.findStrobogrammatic(3)) == sorted([
    "101", "111", "181",
    "609", "619", "689",
    "808", "818", "888",
    "906", "916", "986"
])

# Ensure no leading zeros for n > 1
result = solution.findStrobogrammatic(4)
assert all(not num.startswith("0") for num in result)

# Verify all generated numbers have correct length
result = solution.findStrobogrammatic(5)
assert all(len(num) == 5 for num in result)

# Verify rotational symmetry property
mapping = {
    '0': '0',
    '1': '1',
    '6': '9',
    '8': '8',
    '9': '6'
}

for number in solution.findStrobogrammatic(5):
    rotated = "".join(mapping[d] for d in reversed(number))
    assert rotated == number

# Boundary case: largest allowed n
result = solution.findStrobogrammatic(14)
assert all(len(num) == 14 for num in result)

Test Summary

Test Why
n = 1 Validates single-digit base case
n = 2 Validates smallest even-length construction
n = 3 Validates odd-length recursive construction
No leading zeros Ensures outermost zero handling is correct
Length verification Ensures recursion builds exact target size
Rotational symmetry validation Confirms every output is truly strobogrammatic
n = 14 Tests upper constraint boundary

Edge Cases

Single-Digit Inputs

When n = 1, the number consists of only a center digit. Many implementations mistakenly allow digits like 6 or 9 in the center, but these digits rotate into each other rather than themselves. Only 0, 1, and 8 are valid single-digit strobogrammatic numbers. The implementation handles this explicitly in the current_length == 1 base case.

Leading Zeros

A very common bug is accidentally generating numbers such as "00" or "0110" for multi-digit inputs. These are invalid because standard numeric representations cannot begin with zero. The implementation prevents this by skipping the ("0", "0") pair only when constructing the outermost layer.

Odd-Length Numbers

Odd-length strobogrammatic numbers require a valid center digit. Some recursive solutions incorrectly assume every position must be paired, which fails for odd lengths. The implementation handles this naturally through the current_length == 1 base case, allowing recursion to terminate with a single valid middle digit.

Large Inputs

For n = 14, the number of generated strings becomes large. A brute-force approach would be completely infeasible because it would attempt to inspect trillions of candidates. The recursive constructive approach remains efficient because it generates only valid numbers and avoids unnecessary computation.