Problem Description
Given a positive integer n, return all strobogrammatic numbers of length n. A strobogrammatic number is a number that appears the same when rotated 180 degrees (flipped upside-down).
Key Insights
- The tricky part is correctly handling the digits that transform into each other when rotated.
- Valid strobogrammatic digit pairs are: ('0','0'), ('1','1'), ('6','9'), ('8','8'), ('9','6').
- For numbers with an odd length, the middle digit must be one of: "0", "1", or "8".
- Recursion (or depth-first search/backtracking) can efficiently generate these numbers by starting from the innermost part and wrapping valid pairs around it.
- Avoid using '0' as the leading digit when forming the outer layer (except for the special case where n == 1).
Space and Time Complexity
Time Complexity: O(5^(n/2)) – The recursive solution generates roughly 5^(n/2) combinations. Space Complexity: O(5^(n/2)) – Space is used to store all generated strobogrammatic numbers.
Solution
We use a recursive approach to build strobogrammatic numbers. The idea is to create a helper function that generates numbers of a given remaining length. The base cases are:
- When the remaining length is 0, return a list with an empty string.
- When the remaining length is 1, return the valid middle digits: ["0", "1", "8"].
For other cases, recursively obtain the list for the inner section of the number, then iterate over all valid strobogrammatic pairs to wrap around each inner solution. When adding the pairs at the outermost level, we skip the pair ("0","0") to avoid numbers with leading zeros. This process ensures that every number is built symmetrically and remains strobogrammatic.