247. Strobogrammatic Number II

O(n) time O(1) space
双指针，从两头往中间枚举所有可能即可

class Solution {
public:
    vector<string> findStrobogrammatic(int n) {
        string s(n, '0');
        v = {"16896891", "018810", "0168968910"};
        dfs(s, 0, n - 1);
        return res;
    }

    void dfs(string &s, int l, int r) {
        if (l > r) {
            res.push_back(s);
            return;
        }
        int k = 0;
        if (l == r) {
            k = 1;
        } else if (l > 0) {
            k = 2;
        }
        for (int n = size(v[k]), i = 0, j = n - 1; i < j; ++i, --j) {
            s[l] = v[k][i];
            s[r] = v[k][j];
            dfs(s, l + 1, r - 1);
        }
    }

    vector<string> res, v;
};

class Solution {
public:
    vector<string> findStrobogrammatic(int n) {
        string s(n, '0');
        vector<string> res;
        find(s, 0, n - 1, res);
        return res;
    }

    void find(string &s, int l, int r, vector<string> &res) {
        if (r < l) { // 如果指针交错，添加结果
            res.push_back(s);
            return;
        }
        string chars;
        if (l == r) { // 如果指针相遇，只有可能是180，包括n为1的情况
            chars = "180081";
        } else if (l == 0) { // 如果指针在两头，则不可能是0
            chars = "18696981";
        } else { // 如果指针在其他位置，则都有可能
            chars = "1869006981";
        }
        for (int i = 0, j = chars.length() - 1; i < j; ++i, --j) {
            s[l] = chars[i];
            s[r] = chars[j];
            find(s, l + 1, r - 1, res);
        }
    }
};