248. Strobogrammatic Number III - cocoder39/coco39_LC GitHub Wiki

class Solution {
public:
    int strobogrammaticInRange(string low, string high) {
        vector<pair<char, char>> sbg{{'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'}, {'9', '6'}};
        int res = 0;
        for (int len = low.length(); len <= high.length(); len++) {
            string str(len, ' ');
            helper(res, str, 0, len - 1, low, high, sbg);
        }
        return res;
     }
private:
    void helper(int& res, string& str, int start, int end, string& low, string& high, vector<pair<char, char>>& sbg) {
        if (start > end) {
            if ((str.length() > low.length() || (str.length() == low.length() && str >= low)) 
            &&  (str.length() < high.length() || (str.length() == high.length() && str <= high))) {
                res++;
            }
            return;
        }
        
        for (auto &i : sbg) {
            if (str.length() > 1 && start == 0 && i.first == '0') {
                continue;
            }
            if (start == end && (i.first == '6' || i.first == '9')) {
                continue;
            }
            str[start] = i.first;
            str[end] = i.second;
            helper(res, str, start + 1, end - 1, low, high, sbg);
        } 
        
    }
};