Fork me on GitHub

strobogrammatic-number-ii

Posted on

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.

Example:

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

Solution

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
26
27
28
29
30
31
class Solution {
public:
    vector<string> findStrobogrammatic(int n) {
        return helper(n, 0);
    }
    
    vector<string> helper(int n, int depth) {
        vector<string> ret;
        if (n < 0) return ret;
        if (n == 0) {
            ret.push_back("");
            return ret;
        }
        if (n == 1) {
            ret.push_back("1");ret.push_back("8");ret.push_back("0");
            return ret;
        }
        
        auto base = helper(n - 2, depth + 1);
        for (auto& item : base) {
            ret.push_back('6' + item + '9');
            ret.push_back('9' + item + '6');
            ret.push_back('1' + item + '1');
            ret.push_back('8' + item + '8');
            if (depth != 0) ret.push_back('0' + item + '0');
        }
        
        return ret;
    }

};