Leetcode 248 Strobogrammatic Number III

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.

For example,
Given low = "50", high = "100", return 3. Because 69, 88, and 96 are three strobogrammatic numbers.

Note:
Because the range might be a large number, the low and high numbers are represented as string.

Solution 1: brute force dfs all possible combinations and count the once <max and >min

 public class Solution {  
   public int strobogrammaticInRange(String low, String high) {  
     int m=low.length();  
     int n=high.length();  
     if (m>n) return 0;  
     if (m==n && low.compareTo(high)>0) return 0;  
     int[] count=new int[1];  
     for (int i=m; i<=n; i++) {  
       String lo="L";  
       String hi="H";  
       if (i==m) lo=low;  
       if (i==n) hi=high;  
       char[] c=new char[i];  
       dfs(c,0,i-1,lo,hi,count);  
     }  
     return count[0];  
   }  
   private void dfs(char[] c, int i, int j, String lo, String hi, int[] count) {  
     if (i>j) {  
       String one=new String(c);  
       if (!lo.equals("L") && one.compareTo(lo)<0) return;  
       if (!hi.equals("H") && one.compareTo(hi)>0) return;  
       count[0]++;  
     }  
     else {  
       if (i>0 || (i==0 && i==j)) {  
         c[i]='0'; c[j]='0';  
         dfs(c,i+1,j-1,lo,hi,count);  
       }  
       if (i!=j) {  
         c[i]='6';c[j]='9';  
         dfs(c,i+1,j-1,lo,hi,count);  
         c[i]='9';c[j]='6';  
         dfs(c,i+1,j-1,lo,hi,count);  
       }  
       c[i]='1';c[j]='1';  
       dfs(c,i+1,j-1,lo,hi,count);  
       c[i]='8';c[j]='8';  
       dfs(c,i+1,j-1,lo,hi,count);  
     }  
   }  
 }