Concise JAVA solution, Time (hight.length()), 11ms, beats 96% with detailed comment


  • 0
    public class Solution {
        /* 
         Idea: count the number of Strobogrammatic Number in range(0, low), count1
               count the number of Strobogrammatic Number in range(0, high), count2
               if low itself is a Strobogrammatic Number, return count2 - count1 + 1, otherwise return count2 - count1;
               
         Method:
               1) Construct a table to save the total count of Strobogrammatic Number of a certain length
               e.g. len = 1, count = 3;
                    len = 2, count = 4;
                    len = 3, count = 12;
                    ...
                    rule: when len > 3, count[len] = count[len - 2] * 5; 
                        e.g. len = 4, count = 4 * 5   
                             len = 5, count = 12 * 5
                             len = 6, count = 4 * 5 * 5
                             ...
                This table saves a huge amount of time for this problem
                
               2) Given a string of length 6, for example "123456"
                  Total count of Strobogrammatic Number can be divided into two parts
                  first part is sum of count[1], count[2], count[3], ... count[len - 1]
                  second part is the count of Strobogrammatic Number from "000000" to "123456"
                  
          Analysis: Time O(high.length())
                    real time: 11ms, beats 96 %, cool huh?
         */
        int[] table;
        int[] sum;
        char[][] pair = {{'0', '0'}, {'1', '1'}, {'8', '8'}, {'6', '9'}, {'9', '6'}};
        int count = 0;
        public int strobogrammaticInRange(String low, String high) {
            if (low.length() > high.length() || (low.length() == high.length() && low.compareTo(high) > 0)) {
                return 0;
            }
            int len = Math.max(high.length(), 4);
            table = new int[len];
            sum = new int[len];
            table[1] = 3; sum[1] = 3;
            table[2] = 4; sum[2] = 7;
            table[3] = 12; sum[3] = 19;
            for (int i = 4; i < len; i ++) {
                table[i] = table[i - 2] * 5;
                sum[i] = sum[i - 1] + table[i];
            }
            int count1 = getCount(low, true) + sum[low.length() - 1];
            int count2 = getCount(high, false) + sum[high.length() - 1];
            return count2 - count1;
        }
        
        public int getCount(String s, boolean low) {
            count = 0;
            helper(s, new char[s.length()], low, 0, s.length() - 1);
            return count;
        }
        
        public void helper(String s, char[] arr, boolean low, int left, int right) {
            if (left > right) {
                String newS = new String(arr);
                int res = newS.compareTo(s);
                if (res < 0) {
                    count ++;
                } else {
                    if (res == 0 && !low) {
                        count ++;
                    }
                }
                return;
            }
            int start = (left == 0 && right != 0) ? 1 : 0;
            int end = left == right ? 3 : 5;
            for (int i = start; i < end; i ++) {
                arr[left] = pair[i][0];
                arr[right] = pair[i][1];
                helper(s, arr, low, left + 1, right - 1);
            }
        }
    }
    

Log in to reply
 

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