Description
Given an integer n, return all the strobogrammatic numbers that are of length n. You may return the answer in any order.
A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
Example 1:
Input: n = 2 Output: ["11","69","88","96"]
Example 2:
Input: n = 1 Output: ["0","1","8"]
Constraints:
1 <= n <= 14
Solutions
Solution 1: Recursion
If the length is 1, then the strobogrammatic numbers are only 0, 1, 8; if the length is 2, then the strobogrammatic numbers are only 11, 69, 88, 96.
We design a recursive function dfs(u), which returns the strobogrammatic numbers of length u. The answer is dfs(n).
If u is 0, return a list containing an empty string, i.e., [""]; if u is 1, return the list ["0", "1", "8"].
If u is greater than 1, we traverse all the strobogrammatic numbers of length u - 2. For each strobogrammatic number v, we add 1, 8, 6, 9 to both sides of it, and we can get the strobogrammatic numbers of length u.
Note that if u ≠ n, we can also add 0 to both sides of the strobogrammatic number.
Finally, we return all the strobogrammatic numbers of length n.
The time complexity is O(2^{n+2}).
Similar problems:
class Solution: def findStrobogrammatic(self, n: int) -> List[str]: def dfs(u): if u == 0: return [''] if u == 1: return ['0', '1', '8'] ans = [] for v in dfs(u - 2): for l, r in ('11', '88', '69', '96'): ans.append(l + v + r) if u != n: ans.append('0' + v + '0') return ans return dfs(n)(code-box)
