Description
https://leetcode.com/problems/strobogrammatic-number-ii/
A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
Find all strobogrammatic numbers that are of length = n.
Example:
Input: n = 2
Output: ["11","69","88","96"]
Explanation
recursive
Python Solution
class Solution:
def findStrobogrammatic(self, n: int) -> List[str]:
return self.helper(n, n)
def helper(self, current_length, n):
if current_length == 0:
return [""]
if current_length == 1:
return ["0", "1", "8"]
result = []
subs = self.helper(current_length - 2, n)
for sub in subs:
if current_length != n:
result.append("0" + sub + "0")
result.append("6" + sub + "9")
result.append("9" + sub + "6")
result.append("8" + sub + "8")
result.append("1" + sub + "1")
return result
- Time Complexity: ~N
- Space Complexity: ~N