https://leetcode.com/problems/strobogrammatic-number-ii/
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
- code
class Solution:
def findStrobogrammatic(self, n: int) -> List[str]:
if n == 1: return ['0','1','8']
res = []
dic = {'6':'9','9':'6','0':'0','1':'1','8':'8'}
def backtracking(left, path):
if left < 0: return
if left == 0:
res.append("".join(path))
return
if left == n:
for v in ['6','9','1','8']:
backtracking(left - 1, path + [v])
elif n & 1 and left == n // 2 + 1:
for v in ['0','1','8']:
backtracking(left - 1, path + [v])
elif left > n // 2:
for v in ['6','9','0','1','8']:
backtracking(left - 1, path + [v])
else:
pair_index = left - 1
backtracking(left - 1, path + [dic[path[pair_index]]])
backtracking(n, [])
return res
- code
class Solution:
def findStrobogrammatic(self, n: int) -> List[str]:
pairs = [
['0', '0'], ['1', '1'],
['6', '9'], ['8', '8'], ['9', '6']
]
curlen = n % 2
q = deque(['0','1','8']) if curlen == 1 else deque([''])
while curlen < n:
curlen += 2 # have to be here before for loop
for _ in range(len(q)):
cur = q.popleft()
for p in pairs:
if curlen != n or p[0] != '0':
q.append(p[0] + cur + p[1])
return q