JAVA 0ms solution (99.5%)


  • 13
    S

    Basic Idea:

    return all valid nums under upper (inclusive) - all valid nums under low (exclusive).

    Suppose upper has length len. The numbers of valid nums of len_i's < len, can be very efficiently computed using recursion or Math.pow();.

    For valid nums with len, construct them all and aggressively discard them if they are higher than upper (pruning). After all, char array comparison is cheap : if(compareCharArray(chs, upper, i) > 0) break;

    public class Solution {
        private static char[][] pairs = new char[][]{{'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'}, {'9', '6'}};
        public int strobogrammaticInRange(String low, String high) {
            if(low.length()>high.length() || low.length()==high.length() && high.compareTo(low)<0) return 0;
            return strobogrammaticInRangeFrom0(high, true) - strobogrammaticInRangeFrom0(low, false);
        }
        private int strobogrammaticInRangeFrom0(String num, boolean inclusive){
            int len = num.length();
            if(len == 1){
                if(num.charAt(0) == '0')        return inclusive ? 1 : 0;       // 0?
                else if(num.charAt(0) == '1')   return inclusive ? 2 : 1;       // 0,1?
                else if(num.charAt(0) < '8')    return 2;                       // 0,1
                else if(num.charAt(0) == '8')   return inclusive ? 3 : 2;       // 0,1,8?
                else                            return 3;                       // 0,1,8
            }
            int sum = 0;
            for(int i = 1; i < len; i++)
                sum += strobogrammaticDigit(i, true);
            sum += strobogrammaticInRangeSameDigits(new char[len], 0, len - 1, num.toCharArray(),inclusive);
            return sum;
        }
        private int strobogrammaticInRangeSameDigits(char[] chs, int i, int j, char[] upper, boolean inclusive){
            int sum = 0;
            if(i > j){
                if( inclusive && compareCharArray(upper, chs, chs.length-1 ) >= 0 || !inclusive && compareCharArray(upper, chs, chs.length-1) > 0 )    return 1;
                else    return 0;
            }
            for(char[] pair: pairs){
                if(i == 0 && pair[0] == '0' || i==j && (pair[0] == '6' || pair[0] == '9') )     continue;
                chs[i] = pair[0];
                chs[j] = pair[1];
                if(compareCharArray(chs, upper, i) > 0)     break;
                sum += strobogrammaticInRangeSameDigits(chs, i+1, j-1, upper, inclusive);
            }
            return sum;
        }
        private int strobogrammaticDigit(int digit, boolean outside){
            if(digit == 0)      return 1;
            if(digit == 1)      return 3;
            return outside? strobogrammaticDigit(digit-2, false)*4: strobogrammaticDigit(digit-2, false)*5;
        }
        private int compareCharArray(char[] arr1, char[] arr2, int idx){
            for(int i = 0; i <= idx; i++)
                if(arr1[i] == arr2[i])          continue;
                else if(arr1[i] > arr2[i])      return 1;
                else                            return -1;
            return 0;
        }
    }

  • 0
    M

    great, what is the space complexity?


  • 0
    I

    Same 0ms, time O(logN), space O(1), N is the output, non-recursive.

    static final int[] FIVE = {0, 1, 6, 8, 9};
    static final int[] THREE = {0, 1, 8};
    public int strobogrammaticInRange(String low, String high) {
        int ans = 0, m = low.length(), n = high.length();
        if (m > n || m == n && low.compareTo(high) > 0) return 0;
        ans = helper(m, low, true);
        for (int i = m + 1; i <= n; ++i) {
            ans += helper(i, null, true);
        }
        return ans - helper(n, high, false);
    }
    int helper(int n, String lo, boolean inclusive) {
        int ans = 0;
        boolean same = true;
        for (int i = 0; i < n/2; ++i) {
            ans *= 5;
            if (!same) continue;
            ans += lo == null ? 4 : count(i, lo, FIVE);
            if (lo == null || lo.charAt(i) > '1' && lo.charAt(i) < '8' && lo.charAt(i) != '6') same = false;
        }
        if (n % 2 == 1) {
            ans *= 3;
            if (same) {
                ans += count(n/2, lo, THREE); // lo is not null. n > 1, not same; n = 1, it's low.
                if (lo.charAt(n/2) > '1' && lo.charAt(n/2) != '8') same = false;
            }
        }
        if (same) {
            String s = get(lo);
            if (s.compareTo(lo) > 0 || inclusive && s.equals(lo)) ans++;
        }
        return ans;
    }
    int count(int i, String lo, int[] arr) {
        int cnt = 0, lower = lo.charAt(i) - '0';
        for (int d : arr) {
            if (d > lower) cnt++;
        }
        return cnt;
    }
    String get(String str) {
        int n = str.length();
        StringBuilder sb = new StringBuilder(str.substring(0, (n + 1)/2));
        for (int i = n/2 - 1; i >= 0; --i) {
            if (str.charAt(i) == '6') sb.append('9');
            else if (str.charAt(i) == '9') sb.append('6');
            else sb.append(str.charAt(i));
        }
        return sb.toString();
    }
    

Log in to reply
 

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