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.

一道非常丧心病狂的题。大体思路是，答案 = 和high相同长度的数字里面的strobo的数量 - 和(low-1)相同长度的数字里面的strobo的数量 + 从low长度到high长度-1的数字里面strobo的数量

但是除了恶心人的edgecase， 比如high<low，还有更恶心人的，需要考虑第一位数字是0 1 6 8 9之一，但是末尾数比对应的数字大或者小都要考虑一下。大的话就没事了，小的话得-1（to long and back to sting）。最后别忘了substr的第二位是len，不是end

class Solution {
public:
    int strobogrammaticInRange(string low, string high) {
        if (stol(high) < stol(low))
            return 0;
            
        string low_ = to_string(stol(low)-1);
        int len1 = (low == "0")? 1:low_.size();
        int len2 = high.size();
        int ans = CountNBelow(high, "out");
        ans -= (low != "0")? CountNBelow(low_, "out"):0;
        // cout << "in place ans = " << CountNBelow(high) << " - " << CountNBelow(low_) << " = " << ans << endl;
        for (int l=len1; l<len2; ++l) {
            ans += CountN(l);
        }
        
        return ans;
        // return CountNBelow("49", "out");
    }
    int CountN(int n) {
        if (n <= 0)
            return 0;
        if (n == 1)
            return 3;
        int n_half = n/2;
        int ans = 4*pow(5,n_half-1); // out * mid
        if (n_half*2 != n)
            ans *= 3; // in
        return ans;
    }
    int CountNBelow(string high, string category="mid") {
        int n = high.size();
        if (n == 0) 
            return 1;
        if (n == 1)
            return ReturnIndex("alone", high[0]);
        
        int n_half = n/2;
        int ans = 0;
        
        ans = ReturnIndex(category, high[0]);
        // cout << ans << endl;
        if ((category == "mid" and find(digits_mid.begin(), digits_mid.end(), high[0]) != digits_mid.end()) or
            (category == "out" and find(digits_out.begin(), digits_out.end(), high[0]) != digits_out.end())) {
            --ans;
            // cout << ans << endl;
            if (n_half*2 != n)
                ans *= pow(5,n_half-1)*3; // 0 1 2 3 4 -> 2
            else
                ans *= pow(5,n_half-1); // 0 1 2 3 4 5 -> 3
            // cout << ans << endl;
            if ((category == "mid" and high[n-1]>=map_mid[high[0]]) or 
                (category == "out" and high[n-1]>=map_out[high[0]])
            ) {
                // cout << high.substr(1,n-2) << ", " << to_string(stol(high.substr(1,n-2))) << endl;
                if (n>2)
                    ans += CountNBelow(high.substr(1,n-2));
                else
                    ++ans;
            }
            else if (n>2) {
                ans += CountNBelow(to_string(stol(high.substr(1,n-2)) - 1));
            }
        }
        else {
            if (n_half*2 != n)
                ans *= pow(5,n_half-1)*3; // 0 1 2 3 4 -> 2
            else
                ans *= pow(5,n_half-1); // 0 1 2 3 4 5 -> 3
        }

        return ans;
    }
    int ReturnIndex(string category, char num) {
        int i = 0;
        if (category == "alone") {
            for (const auto& d:digits_alone) {
                if (num < d)
                    break;
                ++i;
            }
        }
        else if (category == "mid") {
            for (const auto& d:digits_mid) {
                // if (nums[0] < d_pair.first or (nums[0] == d_pair.first and nums[1] < d_pair.second))
                if (num < d)
                    break;
                ++i;
            }
        }
        else if (category == "out") {
            for (const auto& d:digits_out) {
                // if (nums[0] < d_pair.first or (nums[0] == d_pair.first and nums[1] < d_pair.second))
                if (num < d)
                    break;
                ++i;
            }
        }
        return i;
    }
private:
    vector<char> digits_alone{'0','1','8'};
    vector<char> digits_mid{'0','1','6','8','9'};
    vector<char> digits_out{'1','6','8','9'};
    map<char,char> map_mid{{'0','0'},{'1','1'},{'6','9'},{'8','8'},{'9','6'}};
    map<char,char> map_out{{'1','1'},{'6','9'},{'8','8'},{'9','6'}};
};

Runtime: 4 ms, faster than 90.54% of C++ online submissions for Strobogrammatic Number III.
Memory Usage: 7 MB, less than 44.59% of C++ online submissions for Strobogrammatic Number III.