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.

class Solution {
public:
    bool isStrobogrammatic(string num) {
        vector<int> map(10, 0);
        map[0] = 0;
        map[1] = 1;
        map[8] = 8;
        map[6] = 9;
        map[9] = 6;
        for(int i = 0; i < num.size(); i++){
            int digit = num[i] - '0';
            if(digit == 0 || digit == 1 || digit == 8 || digit == 6 || digit == 9){
                if(num[num.size() - 1 - i] - '0' != map[digit]){//num[num.size() - 1 - i] should - '0'
                    return false;
                }
            }
            else{
                return false;
            }
        }
        return true;
    }
};

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

Hint:

1. Try to use recursion and notice that it should recurse with n – 2 instead of n – 1.

first generate the first half of the string, since it’s symmetric.

class Solution {
public:
    char candidates[5] = {'0','1','6','8','9'};
    vector<string> findStrobogrammatic(int n) {
        vector<string> ans;
        string thisAns;
        char symmetric[3] = {'0','1','8'};
        int len = n / 2;;
        if(n % 2 == 1){
            for(int i = 0; i < 3; i++){
                thisAns.push_back(symmetric[i]);//center of the string
                dfs((n + 1) / 2, thisAns, ans);
                thisAns.pop_back();    
            }
        }
        else{
            dfs(n / 2, thisAns, ans);
        }
        for(auto& word : ans){
            for(int i = len - 1; i >= 0; i--){
                if(word[i] == '6'){
                    word.push_back('9');
                }else if(word[i] == '9'){
                    word.push_back('6');
                }
                else{
                    word.push_back(word[i]);    
                }
            }
        }
        return ans;
    }
    void dfs(int n, string& thisAns, vector<string>& ans){
        if(thisAns.size() == n){
            ans.push_back(thisAns);
            return ;
        }
        int i = 0;
        if(thisAns.size() == n - 1) i = 1;//first digit should not be 0
        for(; i < 5; i++){
            thisAns.insert(thisAns.begin(),candidates[i]);
            dfs(n, thisAns, ans);
            thisAns.erase(thisAns.begin());
        }
    }
};