Easy to understand Java solution


  • 0
    K

    The basic idea is to populate or the possible results, when the combination meets the requirements, count[0]++

    public int strobogrammaticInRange(String low, String high) {
            int[] count = {0};
            for(int len = low.length(); len <= high.length(); len++) {
                dfs(low, high, "", len, count);
                dfs(low, high, "0", len, count);
                dfs(low, high, "1", len, count);
                dfs(low, high, "8", len, count);
            }
            return count[0];
        }
        
        public void dfs(String low, String high, String str, int len, int[] count) {
            if(str.length() > len) return;
            if(str.length() == len) {
                if(len != 1 && str.charAt(0) == '0') return;//special case numbers prefix is 0
                if((str.length() == low.length() && str.compareTo(low) < 0) || (str.length() == high.length() && str.compareTo(high) > 0)) return;
                count[0]++;
                return;
            }
            dfs(low, high, "0"+str+"0", len, count);
            dfs(low, high, "1"+str+"1", len, count);
            dfs(low, high, "8"+str+"8", len, count);
            dfs(low, high, "6"+str+"9", len, count);
            dfs(low, high, "9"+str+"6", len, count);
        }
    

Log in to reply
 

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