Problem 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:

First, we use some example to find the pattern. If given n= 4.

1
2
3
4
5
6
7
8
9
n = 0:   none

n = 1:   0, 1, 8

n = 2:   11, 69, 88, 96

n = 3:   101, 609, 808, 906, 111, 619, 818, 916, 181, 689, 888, 986

n = 4:   1001, 6009, 8008, 9006, 1111, 6119, 8118, 9116, 1691, 6699, 8698, 9696, 1881, 6889, 8888, 9886, 1961, 6969, 8968, 9966

Observe n == 0 and n == 2, we can see that the latter one is base on the previous one with [1 1], [6 9], [8 8], [9 6] on both side. The same thing happens on n==1 and n==3.

One thing to notice is that when n == 4, we can not put 0 on each side.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:    
    vector<string> findStrobogrammatic(int n) {
        return find(n, n);
    }
    vector<string> find(int m, int n) { //m: which layer currently at. n: which layer need to reach
        if (m == 0) return {""};
        if (m == 1) return {"0", "1", "8"};
        vector<string> t = find(m - 2, n), res;
        for (auto a : t) {
            if (m != n) res.push_back("0" + a + "0"); //0 and 0 can not be in the front and end
            res.push_back("1" + a + "1");
            res.push_back("6" + a + "9");
            res.push_back("8" + a + "8");
            res.push_back("9" + a + "6");
        }
        return res;
    }
};

time complexity: $O(5^n))$, for every recursive call, there will be 5 different result for every string.
space complexity: $O(n/2))$, stack space

reference:
https://goo.gl/oiRqCY
https://goo.gl/mr3grV