# Java Solution Using DP and Strobogrammatic Number II

• Number of Strobogrammatic numbers follows:

``````f(2*n) = f(2*n-1) + f(2*n-2)*2;
f(2*n+1) = f(2*n) * 3;
n = 1,2,3...   |   f(0) = 1, f(1) = 2;
``````

f(1) is a special case because of 0;

``````public int strobogrammaticInRange(String low, String high) {
int h = high.length(), l = low.length();
if (l > h || h == l && low.compareTo(high) > 0)
return 0;
int[] dp = new int[h + 1];
dp[0] = 1; dp[1] = 2;
for (int i = 2; i <= h; i++) {
dp[i] = i % 2 == 0 ? dp[i - 1] + 2 * dp[i - 2] : dp[i - 1] * 3;
}
dp[1] = 3;
long count = findStrobogrammatic(l).stream().filter(j -> j.compareTo(low) >= 0)
.count() -
findStrobogrammatic(h).stream().filter(j -> j.compareTo(high) > 0)
.count();
for (int i = l + 1; i <= h; i++) {
count += dp[i];
}
return (int) count;
}

public List<String> findStrobogrammatic(int n) {
List<String> ret = new ArrayList<>();
helper(ret, new char[n], 0, n-1);
return ret;
}

private final char[] ipick = {'0', '1', '8', '6', '9'};
private final char[] jpick = {'0', '1', '8', '9', '6'};
private void helper(List<String> ret, char[] tmp, int i, int j) {
if (i > j) {
}
if (i == j){
for (int k = 0; k < 3; k++) {
tmp[i] = ipick[k];
helper(ret, tmp, i+1, j-1);
}
} else {
for (int k = i == 0 ? 1 : 0; k < 5; k++) {
tmp[i] = ipick[k];
tmp[j] = jpick[k];
helper(ret, tmp, i+1, j-1);
}
}
}``````

• I tested your solution. I did't find DP solution make any improvement in execution time, and it is even slower!

• Well, it's depend on the test cases. Also, I just simply use java stream which may slower than normal way by iterate the list.
The code above costs 110ms in the Leetcode OJ. I just test the normal method to iterate the list and the result became 25ms.

• This part is slow - as we only need count, not the really string.
long count = findStrobogrammatic(l).stream().filter(j -> j.compareTo(low) >= 0)
.count() -
findStrobogrammatic(h).stream().filter(j -> j.compareTo(high) > 0)
.count();

-find same ideas code here: https://discuss.leetcode.com/topic/44718/java-1ms-solution-with-comments-in-the-code

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