- 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.
- Note:
Because the range might be a large number, the low and high numbers are represented as string.
- public class Solution {
- private int count = 0;
- public int strobogrammaticInRange(String low, String high) {
- find(low, high, "");
- find(low, high, "0");
- find(low, high, "1");
- find(low, high, "8");
- return count;
- }
- private void find(String low, String high, String s){
- //all possible strobogrammatic numbers that are needed to account for
- //must have the length of [low.length(), high.length()]
- if(s.length()>= low.length() && s.length() <= high.length()){
- //ignore the numbers that have the same length with low but are
- //smaller than low. Similarly, ignore the numbers that have the
- //same length with high but are bigger than high
- if(s.length() == low.length() && s.compareTo(low) <0 ||
- s.length() == high.length() && s.compareTo(high)> 0){
- return;
- }
- //ignore the cases where s.equals("0") == false && s.charAt(0) == '0'
- if(!(s.length()> 1 && s.charAt(0) == '0')){
- count++;
- }
- }
- //recursion exit condition: if s.length() is already bigger than the
- //upper bound length, then there is no need to keep searching, exit!
- else if(s.length()> high.length()){
- return;
- }
- find(low, high, "0" + s + "0");
- find(low, high, "1" + s + "1");
- find(low, high, "6" + s + "9");
- find(low, high, "8" + s + "8");
- find(low, high, "9" + s + "6");
- }
- }
- Related Problems
- Strobogrammatic Number II
- [LeetCode] Strobogrammatic Number III
来源: http://www.bubuko.com/infodetail-3301402.html