Java Solution Beats 99.47% with some explanation

• ``````public class Solution {
int[] map = new int[] {4, 3, 3, 3, 3, 3, 2, 2, 1, 0};
int[] centermap = new int[] {2, 1, 1, 1, 1, 1, 1, 1, 0, 0};
int[] pair = new int[] {0, 1, -1, -1, -1, -1, 9, -1, 8, 6};
public int strobogrammaticInRange(String low, String high) {
int cnt = 0;
int lowBigger = greater(low, high);
if(lowBigger > 0) return cnt;
if(lowBigger == 0) return isStrobogrammatic(low) ? cnt + 1 : cnt;
cnt += strobogrammaticNotLessThanKWithSameDigits(low);
for(int i = low.length() + 1;i <= high.length();i++)
cnt += strobogrammaticWithKDigits(i);
cnt -= strobogrammaticNotLessThanKWithSameDigits(high);
if(isStrobogrammatic(high)) ++cnt;
return cnt;
}
private int greater(String a, String b){
if(a.length() != b.length()) return a.length() > b.length() ? 1 : -1;
for(int i = 0;i < a.length();i++){
if(a.charAt(i) > b.charAt(i)) return 1;
if(a.charAt(i) < b.charAt(i)) return -1;
}
return 0;
}
private boolean isStrobogrammatic(String a){
int i = 0, j = a.length() - 1;
while(i <= j){
int l = a.charAt(i) - '0', r = a.charAt(j) - '0';
if(pair[l] < 0 || pair[l] != r) return false;
++i;
--j;
}
return true;
}
private int strobogrammaticWithKDigits(int k){
if(k == 1) return 3;
int cnt = 4;
int i = 2, j = k - 1;
while(i < j){
cnt *= 5;
++i;
--j;
}
if(i == j) cnt *= 3;
return cnt;
}
private int strobogrammaticNotLessThanKWithSameDigits(String k){
if(k.length() == 0) return 0;
int cnt = 0;
if(k.length() == 1){
int cur = k.charAt(0) - '0';
cnt += centermap[cur];
if(cur == 0 || cur == 1 || cur == 8) ++cnt;
return cnt;
}
cnt += strobogrammaticNotLessThanKWithSameDigits(k, 0, k.length() - 1, false);
return cnt;
}
private int strobogrammaticNotLessThanKWithSameDigits(String k, int left, int right, boolean bigger){
int cnt = 0;
if(left > right){
return cnt;
}
int l = k.charAt(left) - '0', r = k.charAt(right) - '0';
if(left + 1 == right){
if(pair[l] > r || (pair[l] == r && !bigger)) ++cnt;
}
if(left == right){
cnt += centermap[l];
if(!bigger && (l == 0 || l == 1 || l == 8)){
++cnt;
}
return cnt;

}
int restdigits = right - left - 1;
cnt += map[l] * Math.pow(5, restdigits / 2);
if(restdigits % 2 == 1) cnt *= 3;
if(l == 0 || map[l - 1] > map[l]){
int p = pair[l];
if(p > r) bigger = false;
if(p < r) bigger = true;
cnt += strobogrammaticNotLessThanKWithSameDigits(k, left + 1, right - 1, bigger);
}
return cnt;
}
}``````

• @houliang
The main idea is that we don't want to generate all numbers. it would be slow and waste many space. It's easy to implement a function that calculate the number of strobogrammatic numbers with k digits.
Then we want to calculate that if there is a lower bound, how many strobo numbers with k digits could we have?
That could be solved by using D&C. The logic is in the function strobogrammaticNotLessThanKWithSameDigits.

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