247. Strobogrammatic Number II (Medium)

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

Hint:

1. Try to use recursion and notice that it should recurse with n - 2 instead of n - 1.

Solution 1: Recursion 23ms

class Solution {
public:
    vector<string> findStrobogrammatic(int n) {
        return dfs(n,n);
    }

    vector<string> dfs(int n, int size) {
        if (n == 0) return {""};
        if (n == 1) return {"0","1","8"};
        vector<string> res;
        for (auto& a: dfs(n-2,size)) {
            if (n < size) res.push_back('0'+a+'0');
            res.push_back('1'+a+'1');
            res.push_back('8'+a+'8');
            res.push_back('6'+a+'9');
            res.push_back('9'+a+'6');
        }
        return res;
    }
};

Solution 2: Iterative 32ms

这道题还有迭代的解法，感觉也相当的巧妙，需要从奇偶来考虑，奇数赋为0,1,8，偶数赋为空，如果是奇数，就从i=3开始搭建，因为计算i=3需要i=1，而我们已经初始化了i=1的情况，如果是偶数，我们从i=2开始搭建，我们也已经初始化了i=0的情况，所以我们可以用for循环来搭建到i=n的情况，思路和递归一样，写法不同而已，参见代码如下：

vector<string> findStrobogrammatic(int n) {
    vector<string> one{"0","1","8"}, zero{""}, res = zero;
    if (n%2) res = one;
    // i start from 3(1) or 2(0)
    for (int i = (n%2)+2; i <= n; i+=2) {
        vector<string> t;
        for (auto a: res) {
            if (i < n) t.push_back('0'+a+'0');
            t.push_back('1'+a+'1');
            t.push_back('8'+a+'8');
            t.push_back('6'+a+'9');
            t.push_back('9'+a+'6');
        }
        res = t;
    }
    return res;
}