Java 2ms solution, I think it is easy to understand, but extremely long ...


  • 0
    L

    The basic idea is:

    1. separate all the numbers by length

    2. within the same length, separate all the numbers by first character.

      private static Map<Character, Character> lookup = new HashMap<Character, Character>();
      private static Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
      static {
      lookup.put('0', '0');
      lookup.put('1', '1');
      lookup.put('8', '8');
      lookup.put('6', '9');
      lookup.put('9', '6');
      }

      public int strobogrammaticInRange(String low, String high) {
      int result = 0;
      int lowLength = low.length();
      int highLength = high.length();

      if (lowLength > highLength || lowLength == highLength && low.compareTo(high) > 0) {
      	return 0;
      }
      
      if (lowLength == highLength) {
      	result = countSameLength(low, high);
      } else {
      	result += countSameLength(low, getRepeat(lowLength, '9'));
      	result += countSameLength('1' + getRepeat(highLength - 1, '0'), high);
      	for (int i = lowLength + 1; i <= highLength - 1; i++) {
      		result += countFull(i, true);
      	}
      }
      
      return result;
      

      }

      private int countSameLength(String low, String high) {
      int result = 0;

      int length = low.length();
      
      if (length == 0) {
      	return 1;
      }
      
      char firstLow = low.charAt(0);
      char firstHigh = high.charAt(0);
      char lastLow = low.charAt(length - 1);
      char lastHigh = high.charAt(length - 1);
      
      if (length == 1) {
      	for (char i = firstLow; i <= firstHigh; i++) {
      		if (i == '0' || i == '1' || i == '8') {
      			result++;
      		}
      	}
      
      	return result;
      }
      
      if (firstLow == firstHigh) {
      	if (lookup.containsKey(firstLow)) {
      		result = countSameLength(low.substring(1, length - 1), high.substring(1, length - 1));
      		if (isStrobogrammatic(low, 1, length - 2) && lookup.get(firstLow) < lastLow)
      			result--;
      		if (isStrobogrammatic(high, 1, length - 2) && lookup.get(firstHigh) > lastHigh)
      			result--;
      	} else {
      		result = 0;
      	}
      
      	return result;
      }
      
      int numFull = 0;
      for (char c = (char) (firstLow + 1); c < firstHigh; c++) {
      	if (lookup.containsKey(c)) {
      		numFull++;
      	}
      }
      if (numFull > 0) {
      	result += numFull * countFull(length - 2, false);
      }
      
      result += countSameLength(low, firstLow + getRepeat(length - 1, '9'));
      result += countSameLength(firstHigh + getRepeat(length - 1, '0'), high);
      
      return result;
      

      }

      private static int countFull(int i, boolean outer) {
      if (i == 0) {
      return 1;
      } else if (i == 1) {
      return 3;
      } else {
      if (outer) {
      return 4 * countFull(i - 2, false);
      } else {
      Integer result = counts.get(i);
      if (result == null) {
      result = 5 * countFull(i - 2, false);
      counts.put(i, result);
      }

      		return result;
      	}
      }
      

      }

      private String getRepeat(int i, char c) {
      StringBuilder output = new StringBuilder();
      while (i-- > 0) {
      output.append(c);
      }
      return output.toString();
      }

      private boolean isStrobogrammatic(String s, int start, int end) {
      while (start <= end) {
      Character expectedEnd = lookup.get(s.charAt(start++));
      if (expectedEnd == null || !expectedEnd.equals(s.charAt(end--))) {
      return false;
      }
      }

      return true;
      

      }


Log in to reply
 

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