# 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"].

## Thoughts

找到所有长度为n的对称数，每个数都以str形式。根据对称数的定义不断往两边拓展，有n为奇数或偶数两种情况。

## Code

```java
class Solution {
public:
    vector<string> findStrobogrammatic(int n) {
        vector<string> res;
        int start = 0;
        if (n & 1 == 1) {
            res.push_back("0");
            res.push_back("1");
            res.push_back("8");
            start = 1;
        } else res.push_back("");
        for (int i = start; i < n; i += 2) {
            vector<string> r;
            for (auto s : res) {
                if (i + 2 < n) r.push_back("0" + s + "0");
                r.push_back("6" + s + "9");
                r.push_back("9" + s + "6");
                r.push_back("1" + s + "1");
                r.push_back("8" + s + "8");
            }
            swap(res, r);
        }
        return res;
    }
};
```

```java
class Solution {
    public List<String> findStrobogrammatic(int n) {
        LinkedList<String> queue = new LinkedList<>();
        if (n % 2 == 0) {
            queue.add("");
        } else {
            queue.add("0");
            queue.add("1");
            queue.add("8");
        }

        boolean zero = true, proceed = true;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String str = queue.remove(0);
                if (str.length() == n - 2) {
                    zero = false;
                } else if (str.length() == n) {
                    queue.add(str);
                    return queue;
                }
                if (zero) {
                    queue.add(0 + str + 0);
                }
                queue.add(6 + str + 9);
                queue.add(9 + str + 6);
                queue.add(8 + str + 8);
                queue.add(1 + str + 1);
            }
        }

        return queue;
    }
}
```

## Analysis

时间复杂度O(N!). 一共有O(N!)个这样的strobogrammatic number.


---

# 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://hao-fu-1.gitbook.io/oj/search/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.