A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.
For example,
Given low = "50", high = "100", return 3. Because 69, 88, and 96 are three strobogrammatic numbers.
Given low = "50", high = "100", return 3. Because 69, 88, and 96 are three strobogrammatic numbers.
Note:
Because the range might be a large number, the low and high numbers are represented as string.
Understand the problem:Because the range might be a large number, the low and high numbers are represented as string.
The idea would be very close to the previous problem. So we find all the strobogrammatic numbers between the length of low and high. Note that when the n == low or n == high, we need to compare and make sure the strobogrammatic number we find is within the range.
Code (Java):
public class Solution { private int count = 0; private Map<Character, Character> map = new HashMap<>(); public int strobogrammaticInRange(String low, String high) { if (low == null || low.length() == 0 || high == null || high.length() == 0) { return 0; } fillMap(); for (int n = low.length(); n <= high.length(); n++) { char[] arr = new char[n]; getStrobogrammaticNumbers(arr, 0, n - 1, low, high); } return count; } private void getStrobogrammaticNumbers(char[] arr, int start, int end, String low, String high) { if (start > end) { String s = new String(arr); if ((s.length() == 1 || s.charAt(0) != '0') && compare(low, s) && compare(s, high)) { count++; } return; } for (char c : map.keySet()) { arr[start] = c; arr[end] = map.get(c); if ((start < end) || (start == end && map.get(c) == c)) { getStrobogrammaticNumbers(arr, start + 1, end - 1, low, high); } } } // Return true if s1 <= s2 private boolean compare(String s1, String s2) { if (s1.length() == s2.length()) { if (s1.compareTo(s2) <= 0) { return true; } else { return false; } } return true; } private void fillMap() { map.put('0', '0'); map.put('1', '1'); map.put('8', '8'); map.put('6', '9'); map.put('9', '6'); } }
No comments:
Post a Comment