247. Strobogrammatic Number II

https://leetcode.com/problems/strobogrammatic-number-ii/description/

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

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;
    }
};

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.