# my method using DP, not very fast.

• In my code, I use dp to calculate the number between lowlen and highlen. The dp array, contains a Pair object.
For example: when len = 2 , dp[1] = (4,1) .

Because when len = 2, there are five combinations: "00" , "11" , "69" , "88" , "96". We keep the last four results as the final result of this length. But even though "00" is not a result for this length, it can also contributes to the next length, so we should keep it.

But for the length == low.length() and length == high.length(), we should find all of the results and compare to the bound using "Strobogrammatic Number II".

My code is not very fast(98ms), just to make a new thought. Hopping to help you.

``````public class Solution {
public int strobogrammaticInRange(String low, String high) {
if(low.length() > high.length()) return 0;
int len = high.length();
int res = 0;
if(len >= 2) {
Pair[] dp = new Pair[len];
dp[0] = new Pair(3 , 0);
dp[1] = new Pair(4 , 1);
for(int i = 2 ; i < len ; i++) {
int l = 4*(dp[i-2].l + dp[i-2].r);
int r = dp[i-2].l + dp[i-2].r;
dp[i] = new Pair(l , r);
}
int lowlen = low.length();
int highlen = high.length();
for(int i = lowlen ; i < highlen-1 ; i++) {
res += dp[i].l;
}
}
int count = 0;
List<String> lowlist = dfshelper(low.length() , low.length());
List<String> highlist = dfshelper(high.length() , high.length());
if(low.length() == high.length()) {
for(int i = 0 ; i < lowlist.size() ; i++) {
if(low.compareTo(lowlist.get(i)) <= 0 && high.compareTo(highlist.get(i)) >= 0) {
count++;
}
}
}else {
for(int i = 0 ; i < lowlist.size() ; i++) {
if(low.compareTo(lowlist.get(i)) <= 0) {
count++;
}
}
for(int i = 0 ; i < highlist.size() ; i++) {
if(high.compareTo(highlist.get(i)) >= 0) {
count++;
}
}
}
return count + res;
}

protected List<String> dfshelper(int n , int m) {
if(n == 0) return new ArrayList<String>(Arrays.asList(""));
if(n == 1) return new ArrayList<String>(Arrays.asList("0" , "1" , "8"));
List<String> res = new ArrayList<String>();
List<String> temp = dfshelper(n-2 , m);
for(int i = 0 ; i < temp.size() ; i++) {
if(n != m) res.add("0" + temp.get(i) + "0");
res.add("1" + temp.get(i) + "1");
res.add("6" + temp.get(i) + "9");
res.add("8" + temp.get(i) + "8");
res.add("9" + temp.get(i) + "6");
}
return res;
}

public class Pair {
int l;
int r;
public Pair(int l , int r) {
this.l = l;
this.r = r;
}
}
}
``````

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