Java Solution Beats 99.47% with some explanation


  • 0
    H
    public class Solution {
        int[] map = new int[] {4, 3, 3, 3, 3, 3, 2, 2, 1, 0};
        int[] centermap = new int[] {2, 1, 1, 1, 1, 1, 1, 1, 0, 0};
        int[] pair = new int[] {0, 1, -1, -1, -1, -1, 9, -1, 8, 6};
        public int strobogrammaticInRange(String low, String high) {
            int cnt = 0;
            int lowBigger = greater(low, high);
            if(lowBigger > 0) return cnt;
            if(lowBigger == 0) return isStrobogrammatic(low) ? cnt + 1 : cnt;
            cnt += strobogrammaticNotLessThanKWithSameDigits(low);
            for(int i = low.length() + 1;i <= high.length();i++)
                cnt += strobogrammaticWithKDigits(i);
            cnt -= strobogrammaticNotLessThanKWithSameDigits(high);
            if(isStrobogrammatic(high)) ++cnt;
            return cnt;
        }
        private int greater(String a, String b){
            if(a.length() != b.length()) return a.length() > b.length() ? 1 : -1;
            for(int i = 0;i < a.length();i++){
                if(a.charAt(i) > b.charAt(i)) return 1;
                if(a.charAt(i) < b.charAt(i)) return -1;
            }
            return 0;
        }
        private boolean isStrobogrammatic(String a){
            int i = 0, j = a.length() - 1;
            while(i <= j){
                int l = a.charAt(i) - '0', r = a.charAt(j) - '0';
                if(pair[l] < 0 || pair[l] != r) return false;
                ++i;
                --j;
            }
            return true;
        }
        private int strobogrammaticWithKDigits(int k){
            if(k == 1) return 3;
            int cnt = 4;
            int i = 2, j = k - 1;
            while(i < j){
                cnt *= 5;
                ++i;
                --j;
            }
            if(i == j) cnt *= 3;
            return cnt;
        }
        private int strobogrammaticNotLessThanKWithSameDigits(String k){
            if(k.length() == 0) return 0;
            int cnt = 0;
            if(k.length() == 1){
                int cur = k.charAt(0) - '0';
                cnt += centermap[cur];
                if(cur == 0 || cur == 1 || cur == 8) ++cnt;
                return cnt;
            }
            cnt += strobogrammaticNotLessThanKWithSameDigits(k, 0, k.length() - 1, false);
            return cnt;
        }
        private int strobogrammaticNotLessThanKWithSameDigits(String k, int left, int right, boolean bigger){
            int cnt = 0;
            if(left > right){
                return cnt;   
            }
            int l = k.charAt(left) - '0', r = k.charAt(right) - '0';
            if(left + 1 == right){
              if(pair[l] > r || (pair[l] == r && !bigger)) ++cnt;  
            } 
            if(left == right){
                cnt += centermap[l];
                if(!bigger && (l == 0 || l == 1 || l == 8)){
                    ++cnt;
                }
                return cnt;
                
            }
            int restdigits = right - left - 1;
            cnt += map[l] * Math.pow(5, restdigits / 2);
            if(restdigits % 2 == 1) cnt *= 3;
            if(l == 0 || map[l - 1] > map[l]){
                int p = pair[l];
                if(p > r) bigger = false;
                if(p < r) bigger = true;
                cnt += strobogrammaticNotLessThanKWithSameDigits(k, left + 1, right - 1, bigger);
            }
            return cnt;
        }
    }

  • 0
    H

    @houliang
    The main idea is that we don't want to generate all numbers. it would be slow and waste many space. It's easy to implement a function that calculate the number of strobogrammatic numbers with k digits.
    Then we want to calculate that if there is a lower bound, how many strobo numbers with k digits could we have?
    That could be solved by using D&C. The logic is in the function strobogrammaticNotLessThanKWithSameDigits.


Log in to reply
 

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