0ms C++ solution with detailed explanation


  • 0
    J

    The idea is to find the number of strobogrammatic strings between [0, num] for a given number num. Then the count between range [low, high] is basically the difference between two runs, one for [0, high] and one for [0, low]. One corner case here is that if low is strobogrammatic, we need to exclude it from the count.

    maintain a mapping from a number to its strobogrammatic counterparts, e.g. 0 => 0, 1 => 1, 6 => 9, 8 => 8, 9 => 6.

    helper functions:

    1. isStrobogrammatic(string num): check whether a string is strobogramatic or not.
    2. stroboLengthN(int n): return number of all strobogrammatic numbers of given length n (including numbers with leading zeros, e.g. "0", "080", "0690").
    3. stroboBelow(int v, int d): for a given 1 or 2 digit number v, return number of strobogrammatic numbers <= v that also has 1 or 2 digits, including numbers with leading zeros (e.g. "0", or "00").
    4. sameLengthBelow(string str, bool countZero): a recursive function to find the number of strobogrammatic numbers <= str and has the same length as str. If countZero is set as true, we include numbers with leading zeros, e.g. 0880 is counted for sameLengthBelow(1981, true).

    For a number of length n represented by num, the strobogrammatic numbers between [0, num] are:

    1. Strings with length less than n (obtained by a loop calling stroboLenghtN).
    2. Strings with length n, and most significant digit (MSD) < num[0], and digits 1 to n-2 can form any strobogrammatic strings of length n-2. This part can be calculated by multiplying results between stroboBelow(int v, int d) and stroboLengthN(n-2).
    3. If num[0] is 0, 1, 6, 8, 9. Then we can also have strings with length n, and MSD = num[0]. The number of such strings can be calculated by recursively calling stroboBelow(str) for the sub-string num[1 .. n-1]. But we might over-counted one number, e.g. when num = 98485, then we over-counted 98486. This only happens when num[n-1] is smaller than the counterpart of num[0], and num[1 .. n-1] is strobogrammatic number.

    Corner cases:

    1. low is equal to high, return whether high is a strobogrammatic string.
    2. low is large than high, then return 0. Use a function to test if low is larger than high.

    The solution is pasted below:

    class Solution {
    public:
        Solution() {
            mapping = {0, 1, -1, -1, -1, -1, 9, -1, 8, 6};
        }
        int strobogrammaticInRange(string low, string high) {
            if(low == high) return isStrobogrammatic(high);
            if(isLarger(low, high)) return 0;
            int count1 = countBelow(low);
            int count2 = countBelow(high);
            if(isStrobogrammatic(low)) count1--;
            return count2 - count1;
        }
        bool isLarger(const string& a, const string& b) {
            int m = a.size(), n = b.size();
            if(m != n) return m > n;
            for(int i = 0; i < m; ++i) {
                if(a[i] > b[i]) return true;
                if(a[i] < b[i]) return false;
            }
            return false; //equal, false
        }
    
        //count strobo numbers from 0 to num including num
        int countBelow(string num) {
            int count = 1; //"0"
            for(int n = 1; n < num.size(); ++n) {
                int tmp = stroboLengthN(n);
                if(n == 1) count += tmp-1; //not include zero 
                else count += tmp-tmp/5; //not include zero
            }
            count += sameLengthStroboBelow(num, false);
            return count;
        }
        //count strobogrammatic numbers <= str, with the same length as str (starting with "0" or "1" depending on countZero)
        int sameLengthStroboBelow(string str, bool countZero) {
    	    int n = str.size();
            int count = 0;
            if(n == 1) {
                int v = str[0]-'0';
                count = stroboBelow(v, 1);
                if(!countZero) count --;
            } else if (n == 2) {
                int v = (str[0]-'0')*10 + (str[1]-'0');
                count = stroboBelow(v, 2);
                if(!countZero) count --;
            } else {
                int v1 = (str[0]-'0'), v2 = (str[n-1]-'0');
                //count strobo with first digit being 1 .. v1-1.
                if(v1 > 0) {
                    int tmp = stroboBelow(v1*10-1, 2);
                    if(!countZero) tmp--;
                    count += tmp*stroboLengthN(n-2); 
                }
                string sub = str.substr(1, n-2);
                if(mapping[v1] >= 0) count += sameLengthStroboBelow(sub, true);
                if(v2 < mapping[v1] && isStrobogrammatic(sub)) count--; //avoid overcounting
            }
            return count;
        }
    
        // number of strobos <= v with d digits (including "0" or "00").
        // v is a number between 0-9 (when d = 1) or 0-99 (when d = 2).
        // 1d strobos: "0", "1", "8"
        // 2d strobos: "00", "11", "69", "88", "96"
        int stroboBelow(int v, int d) {
           int count = 0;
           if(d == 1) {
               if(v < 1) count = 1;
               else if(v < 8) count = 2;
               else count = 3;
           } else if(d == 2) {
               if(v < 11) count = 1;
               else if(v < 69) count = 2; //11
               else if(v < 88) count = 3;
               else if(v < 96) count = 4;
               else count = 5;     
           }
           return count;
        }
    
        //count strobo for digit n (can have leading zeros)
        int stroboLengthN(int n) {
            if(n == 0) return 0;
            int count = (n % 2 == 1) ? 3 : 5;
            while(n > 2) {
                n -= 2;
                count *= 5;  
            }
            return count;
        }
    
        bool isStrobogrammatic(string num) {
            int n = num.size();
            for(int i = 0; i < n/2; ++i) {
                char c1 = num[i];
                char c2 = num[n-i-1];
                if( (c1 == '0' && c2 == '0') ||
                    (c1 == '1' && c2 == '1') ||
                    (c1 == '6' && c2 == '9') ||
                    (c1 == '8' && c2 == '8') ||
                    (c1 == '9' && c2 == '6') ) continue;
                return false;
            }
            if(n % 2 == 1) {
                char c = num[n/2];
                if(c != '0' && c != '1' && c != '8') return false;
            }
            return true;
        }
        vector<int> mapping;
    };

Log in to reply
 

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