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.

Example:

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

// Iteration
vector<string> findStrobogrammatic(int n) { // time: O(5^(n / 2)); space: O(5^(n / 2))
    vector<string> res = (n & 0x1) ? vector<string>({"0", "1", "8"}) : vector<string>({""});
    vector<string> tmp; // reused buffer
    for (int i = 0; i < n / 2; ++i) {
        tmp.clear();
        for (const string& str : res) {
            if (i != n / 2 - 1) tmp.push_back("0" + str + "0");
            tmp.push_back("1" + str + "1");
            tmp.push_back("6" + str + "9");
            tmp.push_back("8" + str + "8");
            tmp.push_back("9" + str + "6");
        }
        swap(res, tmp);
    }
    return res;
}

// Recursion
vector<string> helper(int cur_len, const int& n) {
    if (cur_len == 0) return vector<string>({""});
    if (cur_len == 1) return vector<string>({"0", "1", "8"});
    vector<string> sub_strs = helper(cur_len - 2, n);
    vector<string> res;
    for (const string& str : sub_strs) {
        if (cur_len != n) res.push_back("0" + str + "0");
        res.push_back("6" + str + "9");
        res.push_back("9" + str + "6");
        res.push_back("1" + str + "1");
        res.push_back("8" + str + "8");
    }
    return res;
}
vector<string> findStrobogrammatic(int n) { // time: O(5^(n / 2)); space: O(5^(n / 2))
    return helper(n, n);
}