C++ no need to find all possible string(19ms)


  • 0
    E

    An improved version of https://discuss.leetcode.com/topic/31386/concise-java-solution

    roughly half run-time

    class Solution {
    public:
        int strobogrammaticInRange(string low, string high) {
            if( low.size() > high.size() || (low.size() == high.size() && low.compare(high) > 0) ) return 0;
            int ls = low.size(), hs = high.size(), count = 0;
            if( hs - ls > 1) count += countStrobWithLen(ls, hs);
            findStrobogrammatic(low, high, string(ls, '0'), 0, ls-1, count);
            if( hs - ls > 0) findStrobogrammatic(low, high, string(hs, '0'), 0, hs-1, count);
            return count;
        }
        
        void findStrobogrammatic(string& low, string& high, string s, int left, int right, int& count){
            if( left > right ){
                if( ( s.size() == low.size() && s.compare(low) < 0 ) || ( s.size() == high.size() && s.compare(high) > 0 ) )
                    return;
                count++;
                return;
            }
            for(int i = 0; i < 10; i += 2){
                s[left] = x[i];
                s[right] = x[i+1];
                if( (s.size() != 1 && s[0] == '0') || (left == right && x[i] != x[i+1] ) ) continue;
                findStrobogrammatic(low, high, s, left+1, right-1, count);
            }
        }
        
        int countStrobWithLen(int ls, int hs){
            int count = 0;
            for(int i = max(ls + 1, 0); i < hs; i++){
                if(i == 1) {
                    count += 3;
                    continue;
                }
                int j = i/2 - 1, t = 4;
                t *= pow(5, j);
                count += ( i % 2 == 0 ) ? t : 3*t;
            }
            return count;
        }
    private:
         string x = "0011698896";
    };
    

Log in to reply
 

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