Practice/Uber/Leetcode 247. Strobogrammatic Number II

Leetcode 247. Strobogrammatic Number II

CodingOptional

Problem

A mirror number is a number that looks identical when rotated 180 degrees. When you flip these numbers upside down, they appear exactly the same. The digits that maintain recognizable forms when rotated are:

• 0 rotates to 0
• 1 rotates to 1
• 6 rotates to 9
• 8 rotates to 8
• 9 rotates to 6

Given a positive integer n, generate all mirror numbers of length n. Return them as a list of strings in any order.

Note that numbers with leading zeros are not valid except for the single digit "0" when n=1.

Requirements

1. Generate all valid n-digit mirror numbers
2. Each number must read the same when rotated 180 degrees
3. No leading zeros allowed (except "0" itself when n=1)
4. Return results as a list of strings
5. Handle edge cases including n=0 and n=1

Constraints

• 0 ≤ n ≤ 14
• The output list can be returned in any order
• Time complexity: O(5^n) where we explore possible digit combinations
• Space complexity: O(n × 5^n) for storing all valid numbers

Examples

Example 1:

Input: n = 1 Output: ["0", "1", "8"] Explanation: These three single digits look the same when rotated 180 degrees.

Example 2:

Input: n = 2 Output: ["11", "69", "88", "96"] Explanation: Two-digit mirror numbers. Note that "00" is excluded because it has a leading zero.

Example 3:

Input: n = 3 Output: ["101", "111", "181", "609", "619", "689", "808", "818", "888", "906", "916", "986"] Explanation: Three-digit numbers where the first and last digits form mirror pairs, and the middle digit is one of \{0, 1, 8\}.