247. Strobogrammatic Number II (M)

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:

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

我的答案：先构建string_left，然后把string_left旋转180度，接着考虑如果n是奇数中间的string_mid，最后三者组合起来

class Solution {
public:
    vector<string> findStrobogrammatic(int n) {
        if (n <= 0)
            return {};
        if (n == 1)
            return {"0", "1", "8"};
        
        int n_half = n/2;
        
        vector<string> string_left{"1", "6", "8", "9"};
        for (int i=1; i<n_half; ++i) {
            vector<string> string_left_temp = {};
            for (const auto& s : string_left) {
                for (const auto& s_ : {"0", "1", "6", "8", "9"}) {
                    string_left_temp.push_back(s+s_);
                }
            }
            string_left = string_left_temp;
        }
        
        vector<string> string_right = GetStrobo(string_left);
        vector<string> string_mid;
        if (n_half*2 < n) {
            string_mid = {"0", "1", "8"};
        }
        else {
            string_mid = {""};
        }
        
        vector<string> ans;
        for (int i=0; i<string_left.size(); ++i) {
            for (const auto& mid : string_mid)
                ans.push_back(string_left[i] + mid + string_right[i]);
        }
        
        return ans;
    }
    vector<string> GetStrobo(const vector<string>& string_left) {
        int len_out = string_left.size();
        int len_in = string_left[0].size();
        map<char,char> m{
            {'0','0'},
            {'1','1'},
            {'6','9'},
            {'8','8'},
            {'9','6'}
        };
        vector<string> string_right(len_out, string(len_in, ' '));
        for (int i=0; i<len_out; ++i) {
            for (int j=0; j<len_in; ++j)
                string_right[i][len_in-j-1] = m[string_left[i][j]];
        }
        
        return string_right;
    }
};

Runtime: 48 ms, faster than 20.45% of C++ online submissions for Strobogrammatic Number II.
Memory Usage: 24.4 MB, less than 11.20% of C++ online submissions for Strobogrammatic Number II.

好慢啊

看其他submission

class Solution {
public:
    vector<string> findStrobogrammatic(int n) {
//         vector<string> odd_vec = {{"0", "1", "8"}};
//         vector<string> even_vec = {{"11", "69", "88", "96"}};
//         if (n == 2) return even_vec;
//         if (n == 1) return odd_vec;
        
//         even_vec.push_back({"00"});
        
        vector<string> res;
        if (n % 2 == 0) {
            res = {""};
            helper(&res, n / 2);
        } else {
            res = {"0", "1", "8"};
            helper(&res, n / 2);
        }
        return res;
    }
    
    void helper(vector<string>* res, int to_append) {
        if (to_append == 0) return;
        vector<string> cur = *res;
        res->clear();
        for (string s : cur) {
            if (to_append != 1) res->push_back("0" + s + "0");
            res->push_back("1" + s + "1");
            res->push_back("8" + s + "8");
            res->push_back("9" + s + "6");
            res->push_back("6" + s + "9");
        }
        helper(res, to_append - 1);
    }
};

20ms
比较巧妙的是，从中间开始构建，然后控制是否在最外侧，用to_append这个变量来判断