Super fast 0ms 99.52% Java Solution w/ Explanations


  • 0
    O

    ans = all strobogrammatic of [low.length~high.length-1] + all strobogrammatic of of high.length and no larger than high - all strobogrammatic of of low.length and smaller than low.

    public class Solution {
        private static final char[][] stroPairs = {{'0','0'},{'1','1'},{'6','9'},{'8','8'},{'9','6'}};
        
        public int strobogrammaticInRange(String low, String high) {
            char[] h = high.toCharArray(), l = low.toCharArray();
            h[h.length - 1]++;
            if (h.length < l.length || (h.length == l.length && comp(l, h, 0) == 0)) return 0; // low > high
            int sum = 0;
            for (int len = low.length(); len < high.length(); sum += stroN(len), len++);
            return sum + stroSmallerThan(h) - stroSmallerThan(l);
        }
        
        private int stroFullN(int len) {
            if (len == 0) return 1; // ""
            if (len == 1) return 3; // 0,1,8
            return 5 * stroFullN(len - 2); // 0...0,1...1,8...8,6...9,9...6
        }
        
        private int stroN(int len) {
            if (len < 2) return stroFullN(len);
            return 4 * stroFullN(len - 2);
        }
        
        private int stroSmallerThan(char[] limit) { //count the stros WITH limit's length and SMALLER THAN limit.
            int len = limit.length;
            char[] cur = new char[len];
            return stroSmallerThan(0, len - 1, cur, limit);
        }
        
        private int stroSmallerThan(int i, int j, char[] cur, char[] limit) {
            int sum = 0;
            if (j < i)
                return comp(cur, limit, i);
            if (j == i) {
                for (char[] pair : stroPairs)
                    if (pair[0] == pair[1] && pair[0] <= limit[i])
                        if (pair[0] < limit[i])
                            sum++;
                        else {
                            cur[i] = pair[0];
                            sum += comp(cur, limit, i);
                        }
                return sum;
            }
            
            for (char[]  pair : stroPairs) {
                if (pair[0] < limit[i]) {
                    if (i != 0 || pair[0] != '0') 
                        sum += stroFullN(j - i - 1);
                } else
                if (pair[0] == limit[i]) {
                    cur[i] = pair[0];
                    cur[j] = pair[1];
                    sum += stroSmallerThan(i + 1, j - 1, cur, limit);
                }
            }
            return sum;
        }
        
        int comp(char[] cur, char[] limit, int st) { //return 1 if cur < limit else 0
            for (int i = st; i < cur.length; i++) {
                if (cur[i] < limit[i]) return 1;
                else
                if (cur[i] > limit[i]) return 0;
            }
            return 0;
        }
    }

  • 0
    O
    public class Solution {
        public int strobogrammaticInRange(String low, String high) {
            char[] clow = low.toCharArray(), chigh = high.toCharArray();
            clow[clow.length - 1]--;
            if (chigh.length < clow.length || (clow.length == chigh.length && comp(clow, chigh, 0) > 0))
                return 0;
            int ans = 0;
            for (int i = clow.length; i < chigh.length; i++) ans += practicalStrob(i);
            return ans + cntStrobSmallerThan(chigh, new char[chigh.length], 0) - cntStrobSmallerThan(clow, new char[clow.length], 0);
        }
        
        private char[][] cand = {{'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'}, {'9', '6'}};
        
        private int cntStrobSmallerThan(char[] nums, char[] cur, int i) {
            int res = 0, len = nums.length;
            if (i >= (len - 1) / 2 + 1)        // 01234 - 3, 5, 012345 - 3, 6
                return comp(nums, cur, i);
            
            for (char[] pair : cand) {
                if (pair[0] < nums[i] && ((i < len / 2 && (i != 0 || pair[0] != '0')) || (i == len / 2 && (len & 1) > 0 && pair[0] == pair[1])))
                    res += completeStrob(len - 2 * (i + 1));
                else
                if (pair[0] == nums[i]) {
                    cur[i] = pair[0];
                    cur[len - 1 - i] = pair[1];
                    if (pair[0] == cur[i])
                        res += cntStrobSmallerThan(nums, cur, i + 1);
                }
            }
            return res;
        }
        
        private int comp(char[] nums, char[] cur, int i) { // return 1 if cur <= nums
            for (; i < nums.length; i++)
                if (cur[i] > nums[i]) return 0;
            return 1;
        }
        
        private int completeStrob(int len) { // count complete Strob Number
            if (len <= 0) return 1;
            if (len == 1) return 3;
            return 5 * completeStrob(len - 2);
        }
        
        private int practicalStrob(int len) {
            if (len <= 1) return completeStrob(len);
            return 4 * completeStrob(len - 2);
        }
    }

  • 0
    O

    0ms 99.52%, Done it second time


Log in to reply
 

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