247. Strobogrammatic Number II

class Solution {
public:
    vector<string> findStrobogrammatic(int n) {
        if (n % 2) {
            for (int i = 0; i < 3; i++)
                DFS(n - 1, string(1, dig[i].first));
        } else
            DFS(n, "");
        return res;
    }
private:
    vector<string> res;
    vector<pair<char, char>> dig = {{'0', '0'}, {'8', '8'}, {'1', '1'}, {'6', '9'}, {'9', '6'}};
    void DFS(int k, string s) {
        if (k == 0) {
            res.push_back(s);
            return;
        }
        if (k != 2) DFS(k - 2, dig[0].first + s + dig[0].second);
        for (int i = 1; i < 5; i++) DFS(k - 2, dig[i].first + s + dig[i].second);
        return;
    }
};