C++ 0ms solution, without actually generating strobogrammatic numbers, works fast on long strings


  • 0
    S

    The idea is simple: we only count the number of s-numbers of certain length.

    We have a pair of first and last characters that would form a 2-digit s-number: 00,11,69,88,96;
    so, trying to find number of s-numbers of length 6 and below 654321, we go through this numbers:

    • 00 - discard since 0 cannot be in the beginning
    • 11 - any strobogramatic number of length 4 can be in the middle (and the
      number of 'any s-numbers of length x is easily calculated)
    • 69 - only
      those strobogramatic numbers of length 4 can be in the middle, that
      are less than 5432 -> and so we recurse, but this time we allow 0 to
      be in the beginning.

    this method works on very long strings.

    Once we have S(low) and s(High) we just substract one from another, and account for the fact that if low was strobogramatic.

    if low and high are of different length, we adjust the counts. (and discard counts that are from length 1 to min(low.size(),hight.size())-1;, since they are in both cases the same)

        class Solution {
    
        vector<int> twos={0,11,69,88,96};
    
        /**
         * will return count of s-numbers that are of length len and below or equal the boundary of s.
         */
        int stbg(const string& s, bool zero){ 
       
    
            int addZero=zero?1:0;
            int count=0, i=0;
            bool canBuildLastOne=true;
            if(s.size()==0) return 1;
            if(s.size()==1) {
                if(s[0]=='0') return 1;
                else if(s[0]<'8') return 2;
                else return 3;
            }
            
            //first, count numbers that we are sure will have all the possible middle strobogramatic substrings.
            for(i=(zero?0:1);i<twos.size()&&twos[i]/10<s[0]-'0';i++){
                count++;
            } 
            
            count*=allStbgrWithZero(s.size()-2); //multiply by count of ways we coudl make s-number of size()-2;
    
           // count the number of ways to make middle strobogramatic without going over middle boundary. 
            if(twos[i]/10==s[0]-'0'){ 
                string sMid=s.substr(1,s.size()-2);
                int n=10*(s[0]-'0')+s.back()-'0'; //n is the number composed of first and last digit of a string;
                if(n<twos[i]) canBuildLastOne=subtract1(sMid); //what happens is sMid all zeroes? 
                //e.g. there is no strobogrammatic number of length 4 below or equal 1000
                if(canBuildLastOne) 
                    count+=stbg(sMid,true);// it is, in fact, 1*stbg(sMid,true)
            }
            return count;
        }
        bool subtract1(string& s){
            if (s.empty()) return false;
            auto rit=s.rbegin();
            while(rit!=s.rend()&&*rit=='0') {*rit=9;rit++;}
            if(rit==s.rend()) return false;
            else (*rit)--; 
            return true;
        }
        bool isStrob(string s){
            for(int i=0,j=s.size()-1;i<=j;i++,j--){
                if((s[i]=='6'&&s[j]=='9')||\
                    (s[i]=='9'&&s[j]=='6')||\
                    (s[i]=='0'&&s[j]=='0')||\
                    (s[i]=='8'&&s[j]=='8')||\
                    (s[i]=='1'&&s[j]=='1')) continue;
                else return false;
            }
            return true;
        }
        
        int allStbgrWithZero(int len){
            if(!len) return 1;
            if(len==1) return 3;
            if (len==2) return 5;
            return 5*allStbgrWithZero(len-2);
        }
        int allStbgr(int len){
            if(len==1) return 3; //0,1 and 8
            if (len==2) return 4;
            return 4*allStbgrWithZero(len-2);
        }
    public:
        int strobogrammaticInRange(string low, string high) {
            int l=0,h=0,i=1;
            if(low.size()>high.size()) return 0;
            l=stbg(low,false);
            for(int i=low.size();i<high.size();++i){
                h+=allStbgr(i);
            }
            h+=stbg(high,false);
            if(isStrob(low)) h+=1;
            if(h<l) return 0;
            return h-l;
        }
    };

Log in to reply
 

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