[LeetCode] 248. Strobogrammatic Number III

yzd 發(fā)布于2019-08-16 13:50 / 3198人閱讀

Problem

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

class Solution {
    int count = 0;
    public int strobogrammaticInRange(String low, String high) {
        Map map = new HashMap<>();
        map.put("0", "0");
        map.put("1", "1");
        map.put("6", "9");
        map.put("8", "8");
        map.put("9", "6");
        List res = new ArrayList<>();
        for (int len = low.length(); len <= high.length(); len++) {
            dfs(map, low, high, new char[len], 0, len-1, res);
        }
        System.out.println(res);
        return count;
        
    }
    
    private void dfs(Map map, String low, String high, char[] buffer, int left, int right, List res) {
        if (left > right) {
            String num = new String(buffer);
            if ((num.length() == low.length() && num.compareTo(low) < 0) ||
               (num.length() == high.length() && num.compareTo(high) > 0)) {
                return;
            }
            count++;
            res.add(num);
            return;
        }
        
        for (char ch: map.keySet()) {
            if (buffer.length != 1 && left == 0 && ch == "0") continue;
            if (left == right && ch != map.get(ch)) continue;
            buffer[left] = ch;
            buffer[right] = map.get(ch);
            dfs(map, low, high, buffer, left+1, right-1, res);
        }
    }
}