# Super fast 0ms 99.52% Java Solution w/ Explanations

• ans = all strobogrammatic of [low.length~high.length-1] + all strobogrammatic of of high.length and no larger than high - all strobogrammatic of of low.length and smaller than low.

``````public class Solution {
private static final char[][] stroPairs = {{'0','0'},{'1','1'},{'6','9'},{'8','8'},{'9','6'}};

public int strobogrammaticInRange(String low, String high) {
char[] h = high.toCharArray(), l = low.toCharArray();
h[h.length - 1]++;
if (h.length < l.length || (h.length == l.length && comp(l, h, 0) == 0)) return 0; // low > high
int sum = 0;
for (int len = low.length(); len < high.length(); sum += stroN(len), len++);
return sum + stroSmallerThan(h) - stroSmallerThan(l);
}

private int stroFullN(int len) {
if (len == 0) return 1; // ""
if (len == 1) return 3; // 0,1,8
return 5 * stroFullN(len - 2); // 0...0,1...1,8...8,6...9,9...6
}

private int stroN(int len) {
if (len < 2) return stroFullN(len);
return 4 * stroFullN(len - 2);
}

private int stroSmallerThan(char[] limit) { //count the stros WITH limit's length and SMALLER THAN limit.
int len = limit.length;
char[] cur = new char[len];
return stroSmallerThan(0, len - 1, cur, limit);
}

private int stroSmallerThan(int i, int j, char[] cur, char[] limit) {
int sum = 0;
if (j < i)
return comp(cur, limit, i);
if (j == i) {
for (char[] pair : stroPairs)
if (pair[0] == pair[1] && pair[0] <= limit[i])
if (pair[0] < limit[i])
sum++;
else {
cur[i] = pair[0];
sum += comp(cur, limit, i);
}
return sum;
}

for (char[]  pair : stroPairs) {
if (pair[0] < limit[i]) {
if (i != 0 || pair[0] != '0')
sum += stroFullN(j - i - 1);
} else
if (pair[0] == limit[i]) {
cur[i] = pair[0];
cur[j] = pair[1];
sum += stroSmallerThan(i + 1, j - 1, cur, limit);
}
}
return sum;
}

int comp(char[] cur, char[] limit, int st) { //return 1 if cur < limit else 0
for (int i = st; i < cur.length; i++) {
if (cur[i] < limit[i]) return 1;
else
if (cur[i] > limit[i]) return 0;
}
return 0;
}
}``````

• ``````public class Solution {
public int strobogrammaticInRange(String low, String high) {
char[] clow = low.toCharArray(), chigh = high.toCharArray();
clow[clow.length - 1]--;
if (chigh.length < clow.length || (clow.length == chigh.length && comp(clow, chigh, 0) > 0))
return 0;
int ans = 0;
for (int i = clow.length; i < chigh.length; i++) ans += practicalStrob(i);
return ans + cntStrobSmallerThan(chigh, new char[chigh.length], 0) - cntStrobSmallerThan(clow, new char[clow.length], 0);
}

private char[][] cand = {{'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'}, {'9', '6'}};

private int cntStrobSmallerThan(char[] nums, char[] cur, int i) {
int res = 0, len = nums.length;
if (i >= (len - 1) / 2 + 1)        // 01234 - 3, 5, 012345 - 3, 6
return comp(nums, cur, i);

for (char[] pair : cand) {
if (pair[0] < nums[i] && ((i < len / 2 && (i != 0 || pair[0] != '0')) || (i == len / 2 && (len & 1) > 0 && pair[0] == pair[1])))
res += completeStrob(len - 2 * (i + 1));
else
if (pair[0] == nums[i]) {
cur[i] = pair[0];
cur[len - 1 - i] = pair[1];
if (pair[0] == cur[i])
res += cntStrobSmallerThan(nums, cur, i + 1);
}
}
return res;
}

private int comp(char[] nums, char[] cur, int i) { // return 1 if cur <= nums
for (; i < nums.length; i++)
if (cur[i] > nums[i]) return 0;
return 1;
}

private int completeStrob(int len) { // count complete Strob Number
if (len <= 0) return 1;
if (len == 1) return 3;
return 5 * completeStrob(len - 2);
}

private int practicalStrob(int len) {
if (len <= 1) return completeStrob(len);
return 4 * completeStrob(len - 2);
}
}``````

• 0ms 99.52%, Done it second time

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