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))