248. Strobogrammatic Number III

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.

Example:

Input: low = "50", high = "100"
Output: 3 
Explanation: 69, 88, and 96 are three strobogrammatic numbers.

Note: Because the range might be a large number, the low and high numbers are represented as string.

// Backtracking
void helper(const string& low, const string& high, string& str, int left, int right, const unordered_map<char, char>& rotate, int& res) {
    if (left > right) {
        if ((str.length() == low.length() && str < low) || (str.length() == high.length() && str > high) ) return;
        ++res;
        return;
    }
    for (const auto& e : rotate) {
        char orig_left = str[left], orig_right = str[right];
        str[left] = e.first;
        str[right] = e.second;
        if (str.length() != 1 && str[0] == '0') continue;
        if (left == right && e.first != e.second) continue;
        helper(low, high, str, left + 1, right - 1, rotate, res);
        str[left] = orig_left;
        str[right] = orig_right;
    }
}
int strobogrammaticInRange(string low, string high) { // time: O(5^str_len); space: O(str_len)
    unordered_map<char, char> rotate;
    rotate['0'] = '0';
    rotate['1'] = '1';
    rotate['6'] = '9';
    rotate['8'] = '8';
    rotate['9'] = '6';
    int res = 0;
    for (int len = low.length(); len <= high.length(); ++len) {
        string tmp(len, '0');
        helper(low, high, tmp, 0, len - 1, rotate, res);
    }
    return res;
}

void helper(const string& low, const string& high, string& str, int left, int right, const string& rotate, int& res) {
    if (left > right) {
        if ((str.length() == low.length() && str < low) || (str.length() == high.length() && str > high) ) return;
        ++res;
        return;
    }
    for (int i = 0; i < 10; ++i) {
        if (rotate[i] == ' ') continue;
        char orig_left = str[left], orig_right = str[right];
        str[left] = static_cast<char>(i + '0');
        str[right] = rotate[i];
        // any string longer than 1 cannot start with 0
        if (str.length() != 1 && str[0] == '0') continue;
        // the middle char in odd length string
        if (left == right && static_cast<char>(i + '0') != rotate[i]) continue;
        helper(low, high, str, left + 1, right - 1, rotate, res);
        // backtrack
        str[left] = orig_left;
        str[right] = orig_right;
    }
}
int strobogrammaticInRange(string low, string high) {
    const string rotate = "01    9 86";
    int res = 0;
    for (int len = low.length(); len <= high.length(); ++len) {
        string tmp(len, '0');
        helper(low, high, tmp, 0, len - 1, rotate, res);
    }
    return res;
}