# 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.![](/files/-LoJIo1piYk8_dggqYu_)

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/247-strobogrammatic-number-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.