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

• 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";
};
``````

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