C++ 6ms 19 lines with comments


  • 0
    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);
            return totalCnt;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.