Description

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.

Example:

Input: low = "50", high = "100"
Output: 3
Explanation: 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.

Solution

Iteration

这道题其实完全可以利用"Strobogrammatic Number II"中实现的方法，生成长度为len的Strobogrammatic number list。这样我们只需要生成长度在[low.length(), high.length()]之间，且值在[low, high]之间的就行了。

注意这里low, high以及生成的数字都是string！必须调用String.compare来比较大小了。这里注意，比较大小时要提前判断两个string的长度是否相等，否则会出现"52" > "123"的情况！

class Solution {
    public int strobogrammaticInRange(String low, String high) {
        List<String> list = new ArrayList<>();
        for (int l = low.length(); l <= high.length(); ++l) {
            list.addAll(findStrobogrammatic(l));
        }
        
        int count = 0;
        for (String s : list) {
            if ((s.length() == low.length() && s.compareTo(low) < 0)
               || (s.length() == high.length() && s.compareTo(high) > 0)) {
                continue;
            }
            ++count;
        }
        
        return count;
    }
    
    private List<String> findStrobogrammatic(int len) {
        List<String> list = len % 2 == 0 ? 
            Arrays.asList("") : Arrays.asList("0", "1", "8");
        
        for (int i = len % 2 == 0 ? 0 : 1; i < len; i += 2) {
            List<String> newList = new ArrayList<>();
            for (String s : list) {
                if (i + 2 < len) {
                    newList.add("0" + s + "0");
                }
                
                newList.add("1" + s + "1");
                newList.add("6" + s + "9");
                newList.add("8" + s + "8");
                newList.add("9" + s + "6");
            }
            
            list = newList;
        }
        
        return list;
    }
}