246. Strobogrammatic Number

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to determine if a number is strobogrammatic. The number is represented as a string.

For example, the numbers "69", "88", and "818" are all strobogrammatic.

S： loop

    bool isStrobogrammatic(string num) {
        unordered_map<char, char> map;
        map['0'] = '0';
        map['1'] = '1';
        map['8'] = '8';
        map['6'] = '9';
        map['9'] = '6';
        int n = num.size();
        for (int i = 0; i <= n/2; ++i) {
            if (map.find(num[i]) == map.end() || map[num[i]] != num[n - 1 - i]) 
                return false;
        }
        return true;
    }

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.

For example,
Given n = 2, return["11","69","88","96"].

S: DFS O(4^n)

此题要求不能以0开头

    vector<string> findStrobogrammatic(int n) {
        vector<string> pre;
        if (n < 1) return vector<string>{};
        if (n & 1) pre = vector<string> {"0", "1", "8"};  
        else pre = vector<string>{""};  
        return getResult(pre, n / 2);  
    }

    vector<string> getResult(vector<string> pre, int n) {
        if (n == 0) return pre;
        vector<string> result;
        for (string s: pre) {
            if (n > 1) {
                result.push_back('0' + s + '0');
            }
            result.push_back('1' + s + '1');
            result.push_back('8' + s + '8');
            result.push_back('6' + s + '9');
            result.push_back('9' + s + '6');
        }
        return getResult(result, n - 1);
    }