1 ms Java solution with explanation and comments


  • 0
    R

    This idea is as following:

    1. split solution to three parts:
      for numbers with low.length digits, how many strobogrammatic numbers>= low
      for numbers with hi.length digits, how many strobogrammatic numbers<= hi
      for numbers with digits n that lo<n<hi, count the f(n)

      1. for n-digit number, how many strobogrammatic number exist:
        n count
        0 0
        1 3
        2 4
        3 3* 4=12
        4 4* 5=20
        5 12* 5=60
        6 20* 5=100

      so f(n) = 0 when n=0
      =3 when n=1
      =4 when n=2
      =12 when n=3
      = f(n-2) / 4 * 5* 4 = 5*f(n-2) when n>3

      1. core part is count the stro numbers <= hi, with the hi.length digits.
    public class StrobogrammaticNumberIII {
    
    	private char[] compArr = { '0', '1', '6', '8', '9' };
    	private char[] symArr = { '0', '1', '9', '8', '6' };
    	private char[] oneDigitArr = { '0', '1', '8' };
    	public int strobogrammaticInRange(String low, String high) {
    
    		// validation
    		if (low == null || high == null || low.length() == 0 || high.length() == 0
    		        || low.length() > high.length()) {
    			return 0;
    		}
    
    		int count = 0;
    		char[] l = low.toCharArray();
    		char[] h = high.toCharArray();
    
    		if (l.length == h.length) {
    			// count of stro numbers that <=hi
    			int a = countLess(h, 0, h.length);
    			// count of stro numbers that <lo
    			int b = countLess(l, 0, l.length);
    			if (isStroNum(l)) {
    				b--;
    			}
    
    			return a - b;
    		}
    		// count of stro number>=lo in all lo.length-digit numbers
    		count += countNdigit(l.length) - countLess(l, 0, l.length);
    		if (isStroNum(l)) {
    			count++;
    		}
    		// count of stro numbers<=hi
    		count += countLess(h, 0, h.length);
    
    		for (int i = l.length + 1; i < h.length; i++) {
    			count += countNdigit(i);
    		}
    
    		return count < 0 ? 0 : count;
    	}
    
    	private boolean isStroNum(char[] c) {
    
    		for (int i = 0; i <= c.length / 2; i++) {
    			if (c[i] == '0' || c[i] == '1' || c[i] == '8') {
    				if (c[c.length - 1 - i] != c[i]) {
    					return false;
    				}
    			}
    			if (c[i] == '6') {
    				if (c[c.length - 1 - i] != '9') {
    					return false;
    				}
    			}
    			if (c[i] == '9') {
    				if (c[c.length - 1 - i] != '6') {
    					return false;
    				}
    			}
    
    		}
    
    		return true;
    
    	}
    
    	// how many strobogrammatic numbers with n-digits
    	private int countNdigit(int n) {
    		if (n <= 0) {
    			return 0;
    		}
    		if (n == 1) {
    			return 3;
    		}
    		if (n == 2) {
    			return 4;
    		}
    		if (n == 3) {
    			return 12;
    		}
    
    		return countNdigit(n - 2) * 5;
    	}
    
    	/**
    	 * count how many strobogrammatic numbers equals or less than s in all numbers with c.length
    	 * digits count from left to right, if the digit>compArr[k], then count+=countLess(c, index+1,
    	 * n-2) Attention: handle the edge condition such as the most outer layer, n==1, n==2,etc.
    	 * 
    	 * @param c
    	 *            char[]
    	 * @param index
    	 *            starts from 0,add 2 each step
    	 * @param n
    	 *            the length of char array c
    	 * @return count of strobogrammatic numbers
    	 */
    	private int countLess(char[] c, int index, int n) {
    		int count = 0;
    		boolean flag;
    
    		if (n > 0) {
    			int k = 0;
    			// only compare 0,1,8
    			if (n == 1) {
    				for (; k < oneDigitArr.length; k++) {
    					if (c[index] >= oneDigitArr[k]) {
    						count++;
    					}
    				}
    				return count;
    			}
    			// for the outer most layer, do not count{0,0}
    			if (n == c.length) {
    				k++;
    			}
    			for (; k < compArr.length; k++) {
    				if (c[index] > compArr[k]) {
    					count += innerCount(n);
    				} else if (c[index] == compArr[k]) {
    
    					// check the symmetric position
    					flag = c[c.length - 1 - index] >= symArr[k];
    					if (n <= 2) {
    						if (flag) {
    							count++;
    						}
    					} else {
    						count += countLess(c, index + 1, n - 2);
    						char[] innerArr = new char[c.length - 2 * (index + 1)];
    						System.arraycopy(c, index + 1, innerArr, 0, innerArr.length);
    						// when the inner layer is exactly a stro number and the out layer is not
    						// symmetric, count--
    						if (!flag && isStroNum(innerArr)) {
    							count--;
    						}
    					}
    					return count;
    				} else {
    					return count;
    				}
    
    			}
    		}
    
    		return count;
    	}
    
    	// helper method to count the numbers when c[index]>compArr[k]
    	private int innerCount(int n) {
    
    		if (n == 1 || n == 2) {
    			return 1;
    		}
    		if (n == 3) {
    			return countNdigit(n - 2);
    		}
    
    		return countNdigit(n - 2) / 4 * 5;
    
    	}
    
    }
    

    Hope that helps :)


Log in to reply
 

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