# Concise JAVA solution, Time (hight.length()), 11ms, beats 96% with detailed comment

• ``````public class Solution {
/*
Idea: count the number of Strobogrammatic Number in range(0, low), count1
count the number of Strobogrammatic Number in range(0, high), count2
if low itself is a Strobogrammatic Number, return count2 - count1 + 1, otherwise return count2 - count1;

Method:
1) Construct a table to save the total count of Strobogrammatic Number of a certain length
e.g. len = 1, count = 3;
len = 2, count = 4;
len = 3, count = 12;
...
rule: when len > 3, count[len] = count[len - 2] * 5;
e.g. len = 4, count = 4 * 5
len = 5, count = 12 * 5
len = 6, count = 4 * 5 * 5
...
This table saves a huge amount of time for this problem

2) Given a string of length 6, for example "123456"
Total count of Strobogrammatic Number can be divided into two parts
first part is sum of count[1], count[2], count[3], ... count[len - 1]
second part is the count of Strobogrammatic Number from "000000" to "123456"

Analysis: Time O(high.length())
real time: 11ms, beats 96 %, cool huh?
*/
int[] table;
int[] sum;
char[][] pair = {{'0', '0'}, {'1', '1'}, {'8', '8'}, {'6', '9'}, {'9', '6'}};
int count = 0;
public int strobogrammaticInRange(String low, String high) {
if (low.length() > high.length() || (low.length() == high.length() && low.compareTo(high) > 0)) {
return 0;
}
int len = Math.max(high.length(), 4);
table = new int[len];
sum = new int[len];
table[1] = 3; sum[1] = 3;
table[2] = 4; sum[2] = 7;
table[3] = 12; sum[3] = 19;
for (int i = 4; i < len; i ++) {
table[i] = table[i - 2] * 5;
sum[i] = sum[i - 1] + table[i];
}
int count1 = getCount(low, true) + sum[low.length() - 1];
int count2 = getCount(high, false) + sum[high.length() - 1];
return count2 - count1;
}

public int getCount(String s, boolean low) {
count = 0;
helper(s, new char[s.length()], low, 0, s.length() - 1);
return count;
}

public void helper(String s, char[] arr, boolean low, int left, int right) {
if (left > right) {
String newS = new String(arr);
int res = newS.compareTo(s);
if (res < 0) {
count ++;
} else {
if (res == 0 && !low) {
count ++;
}
}
return;
}
int start = (left == 0 && right != 0) ? 1 : 0;
int end = left == right ? 3 : 5;
for (int i = start; i < end; i ++) {
arr[left] = pair[i][0];
arr[right] = pair[i][1];
helper(s, arr, low, left + 1, right - 1);
}
}
}
``````

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