lc247-Strobogrammatic Number II

發表於   |   分類於   |   0 comments   |  

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    vector<vector<string>> res;
public:
    vector<string> findStrobogrammatic(int n) {
        res.push_back({""});
        res.push_back({"0", "1", "8"});
        for (int i = 2; i <= n; i++) {
            res.push_back({});
        }
        recursion(n, true);
        return res[n];
    }
    vector<string> recursion(int n, bool outer) {
        if (res[n].size())    return res[n];
        string s = "";
        vector<pair<string, string>> p = {make_pair("0", "0"), make_pair("1","1"), make_pair("6", "9"), make_pair("8", "8"), make_pair("9", "6")};
        for (int i = outer; i < 5; i++) {
            for (auto j:recursion(n-2, false)) {
                s = p[i].first + j + p[i].second;
                res[n].push_back(s);
            }
        }
        return res[n];
    }
};