class Solution {
    public int strobogrammaticInRange(String low, String high) {
        int count = 0;
        for(int i = low.length(); i <= high.length(); i++){
            if(i%2 == 0){
                count += solve(low, high, "", i);
            }else{
                count += solve(low, high, "0", i);
                count += solve(low, high, "1", i);
                count += solve(low, high, "8", i);
            }
        }
        return count;
    }
    int solve(String low, String high, String cur, int len){
        if(cur.length() == len){
            if((low.length() == len && low.compareTo(cur) > 0)
               || ((high.length() == len && high.compareTo(cur) < 0))) return 0;
            return 1;
        }
        int count = 0;
        if(cur.length() + 2 < len) count += solve(low, high, "0" + cur + "0", len);
        count += solve(low, high, "8" + cur + "8", len);
        count += solve(low, high, "1" + cur + "1", len);
        count += solve(low, high, "9" + cur + "6", len);
        count += solve(low, high, "6" + cur + "9", len);
        return count;
    }
}