Strobogrammatic Number II - Solution & Explanation

Problem Overview: Generate all strobogrammatic numbers of length n. A number is strobogrammatic if it looks the same when rotated 180 degrees. Valid digit pairs are (0,0), (1,1), (6,9), (8,8), and (9,6). The result must include every valid number of length n without leading zeros (except when n = 1).

Approach 1: Brute Force Generation + Validation (O(10^n * n) time, O(n) space)

The most direct idea is to generate every possible n-digit number and check whether it remains valid after a 180-degree rotation. For each candidate, iterate through the digits from both ends and verify the rotation mapping: 0→0, 1→1, 6→9, 8→8, 9→6. Any digit outside this set immediately invalidates the number. This approach performs up to 10^n checks and each validation takes O(n) time, making it extremely slow even for moderate values of n. It demonstrates the property of strobogrammatic numbers but is not practical for interviews.

Approach 2: Recursive Pair Construction (O(5^(n/2)) time, O(5^(n/2)) space)

The efficient approach builds numbers from the center outward using valid strobogrammatic digit pairs. Instead of generating every number, you only place digits that remain valid after rotation. Use recursion to construct smaller strobogrammatic strings of length n-2, then wrap them with valid pairs like "1" + middle + "1" or "6" + middle + "9". The base cases are length 0 (return an empty string) and length 1 (return 0, 1, 8). Avoid placing 0 at the outermost level to prevent leading zeros.

Each recursion level adds symmetric pairs around the inner string. Since there are at most five valid pairs and the recursion depth is roughly n/2, the total number of generated combinations is about 5^(n/2). This directly generates only valid numbers, which is far more efficient than filtering invalid candidates.

The algorithm works naturally with recursion because each valid number can be decomposed into an inner strobogrammatic string plus a symmetric outer pair. The result set is stored using simple string construction, and iteration over candidate pairs is straightforward.

Recommended for interviews: Recursive pair construction is the expected solution. It shows that you recognized the symmetry property of strobogrammatic numbers and avoided brute force enumeration. Mentioning the brute force idea first shows understanding of the problem space, but implementing the recursive construction demonstrates stronger algorithmic thinking.