# Accepted Java Solution

• ``````public class Solution {
public int numLow=0;
public int numHigh=0;
public int strobogrammaticInRange(String low, String high) {
int lenL=low.length();
int lenH=high.length();
if(low.startsWith("-")) low="";
if(high.startsWith("-") || lenL>lenH) return 0;
Map<Integer, Integer> map=new HashMap<Integer, Integer>();
map.put(0, 0); map.put(1, 3);map.put(2, 4); map.put(3, 12); map.put(4, 20);
// when it is over 4, F[i]=F[i-2]*(F[2]+1) because it need also count "00" which is not count by F[2]
for(int i=5;i<=lenH;i++)
map.put(i, 5*map.get(i-2));
getCountHelper(lenL, "", low, true);
getCountHelper(lenH, "", high, false);
int count=0;
for(int i=lenL;i<=lenH-1;i++)
count+=map.get(i);
return Math.max(0, count+numHigh-numLow);
}
public void getCountHelper(int n, String currentStr, String str, boolean isLow){
int len=currentStr.length();
if(len==n){
if(currentStr.compareTo(str)<0){
if(isLow) numLow++;
else numHigh++;
}else if(currentStr.equals(str) && !isLow) numHigh++;
return;
}
if(len>n) return;
if(len==0){
getCountHelper(n, "0", str, isLow);
getCountHelper(n, "1", str, isLow);
getCountHelper(n, "8", str, isLow);
}
if(len!=n-2) getCountHelper(n, "0"+currentStr+"0", str, isLow);
getCountHelper(n, "1"+currentStr+"1", str, isLow);
getCountHelper(n, "6"+currentStr+"9", str, isLow);
getCountHelper(n, "9"+currentStr+"6", str, isLow);
getCountHelper(n, "8"+currentStr+"8", str, isLow);
}
}``````

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