# 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.![](https://176165416-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LoJHphwLiMOHOYPmtrx%2F-LoJHq55n17qGKUSaNW0%2F-LoJIo1piYk8_dggqYu_%2F247_strobogrammatic_number.png?generation=1568003836319109\&alt=media)

**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.

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