247 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.
For example,
Given n = 2, return
["11","69","88","96"].Attempt 1: TLE
The Idea: Build from the base case of an empty array. Notice how the edges do not include zeros, and if this were an odd array, then the center wouldn't contain either 6 or 9.
Complexity: O(5^n) time, but more specifically 4*5*5... for even case and 4*5*5*3 for odd case. The time taken for the deepcopy makes TLE.
import queue
import copy
class Solution:
def findStrobogrammatic(self, n):
"""
:type n: int
:rtype: List[str]
"""
if not n:
return []
sym_pair1 = {'8': '8', '6': '9', '9': '6', '1': '1', '0': '0'}
sym_pair2 = {'8': '8', '6': '9', '9': '6', '1': '1'}
sym_pair3 = {'8': '8', '1': '1', '0': '0'}
root = [''] * n
q = queue.Queue()
q.put((root, 0, n - 1))
final_result = []
while not q.empty():
parent = q.get()
num = parent[0]
left = parent[1]
right = parent[2]
# 6 or 9 cannot be in the center for odd case
if left == right:
pointer_iter = sym_pair3
# all available options
elif left <= right and left != 0 and right != n - 1:
pointer_iter = sym_pair1
# cannot contain 0s on the edges (doesn't produce unique number)
elif left <= right and left == 0 and right == n - 1:
pointer_iter = sym_pair2
# otherwise the array is full
else:
final_result.append(''.join(num))
continue
# append each option
for key, val in pointer_iter.items():
num[left] = key
num[right] = val
q.put((copy.deepcopy(num), left + 1, right - 1))
return final_result
obj = Solution()
print(obj.findStrobogrammatic(13))
Last modified 4yr ago