# C++ 6ms 19 lines with comments

• ``````class Solution {
private:
int left[5] = {'0', '1', '8', '6', '9'}, right[5] = {'0', '1', '8', '9', '6'};
// count the ones out of boundary, maybe smaller than bound, or larger than bound
void getCnt(int& cnt, string& bound, bool smaller, string& cur, int l, int r) {
if (l <= r) {
for (int i = 0; i < 5; i++) {
if ((!l && r && left[i] == '0') || (l == r && left[i] != right[i])) { continue; }
cur[l] = left[i], cur[r] = right[i];
getCnt(cnt, bound, smaller, cur, l + 1, r - 1);
}
} else if ((smaller && cur < bound) || (!smaller && cur > bound)) { cnt--; }
}

public:
int strobogrammaticInRange(string low, string high) {
if (low.length() < 1 || low.length() > high.length()) { return 0; }

// calculate total number for [low.length(), high.length()]
int minLen = low.length(), maxLen = high.length(), totalCnt = 0;
for (int len = minLen; len <= maxLen; len++) {
totalCnt += len == 1 ? 3 : 4 * pow(5, len / 2 - 1) * (len & 1 ? 3 : 1);
}

// calculate and substract the ones (1) smaller than low or (2) larger than high
string cur = string(minLen, ' ');
getCnt(totalCnt, low, true, cur, 0, minLen - 1);
getCnt(totalCnt, high, false, cur = string(maxLen, ' '), 0, maxLen - 1);