247. Strobogrammatic Number II

Tags: Medium Recursion

Links: https://leetcode-cn.com/problems/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.

Example:

Input:  n = 2
Output: ["11","69","88","96"]

---

class Solution {
public:
    vector<string> findStrobogrammatic(int n) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        return build(n, n);
    }

    vector<string> build(int m, int n)
    {
        if (m == 0) return {""};
        if (m == 1) return {"1", "8", "0"};

        vector<string> tmp = build(m - 2, n), res;
        for (auto &e : tmp) {
            if (m != n) res.push_back("0" + e + "0");
            res.push_back("1" + e + "1");
            res.push_back("8" + e + "8");
            res.push_back("6" + e + "9");
            res.push_back("9" + e + "6");
        }

        return res;
    }
};

这道题需要注意0不能作为开头。

迭代的解法：

class Solution {
public:
    vector<string> findStrobogrammatic(int n) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        if (n == 0) return {""};
        if (n == 1) return {"1", "8", "0"};
        vector<string> res{""};
        if (n & 1) res = {"1", "8", "0"};

        for (int i = (n % 2) + 2; i <= n; i += 2) {
            vector<string> tmp;
            for (auto e : res) {
                if (i != n) tmp.push_back("0" + e + "0");
                tmp.push_back("1" + e + "1");
                tmp.push_back("8" + e + "8");
                tmp.push_back("6" + e + "9");
                tmp.push_back("9" + e + "6");
            }
            res = tmp;
        }

        return res;
    }
};