Strobogrammatic Number I, II and III

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to determine if a number is strobogrammatic. The number is represented as a string.

For example, the numbers "69", "88", and "818" are all strobogrammatic.

The first problem is quite easy, based on the definition, we only need to check from the two ends, if the two numbers cannot map to each other, we know it's a false.

public boolean isStrobogrammatic(String num) {
        Map map = new HashMap<>();
        map.put('1', '1');
        map.put('0', '0');
        map.put('6', '9');
        map.put('8', '8');
        map.put('9', '6');

        int left = 0, right = num.length() - 1;
        while (left < right) {
            char c1 = num.charAt(left);
            char c2 = num.charAt(right);
            if (!map.containsKey(c1)
                || !map.containsKey(c2)
                || map.get(c1) != c2
                || map.get(c2) != c1) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Find all strobogrammatic numbers that are of length = n.

For example, Given n = 2, return ["11","69","88","96"].

The second one asks us to list all Strobogrammatic numbers of length n, which naturally we should use backtracking. Use a char array and iterate the chars inside the array, append the numbers to a string until reaches half of its length. For n % 2 != 0, we know there is one single number in the middle, and that number cannot be 6 or 9.  numbers with 0 at the beginning and end if n > 1 doesn't make sense either. I choose to iterate till (n + 1)/ 2 because we can add the single number in the middle to the string. When we add the other half, we only need to insert to the middle and iterate till n/2.

Another way can be adding from middle to two ends, and we track both one number in the middle or two numbers in the middle. I didn't implement this, but this should be faster.

public List findStrobogrammatic(int n) {
        List<string> rst = new ArrayList<>();
        if (n == 0) {
            return rst;
        }
        Map<character, character> map = new HashMap<>();
        map.put('1', '1');
        map.put('0', '0');
        map.put('6', '9');
        map.put('8', '8');
        map.put('9', '6');

        char[] numbers = {'0', '1', '6', '8', '9'};
        getList(n, map, numbers, rst, new StringBuilder(), 0);
        return rst;
    }

    private void getList(int n, Map<character character> map, char[] numbers, List<string> rst, StringBuilder curr, int start) {
        if (curr.length() == (n + 1) / 2) {
            if ((n > 1 && curr.charAt(0) == '0')
                || (n % 2 != 0 && (curr.charAt((n - 1) / 2) == '6' || curr.charAt((n - 1) / 2) == '9'))) {
                return;
            }
            for (int i = 0; i < n/2; i++) {
                curr.insert((n + 1)/2, curr.charAt(i));
                rst.add(curr.toString());
            }
        }
        for (int i = start; i < numbers.length; i++) {
            curr.append(i);
            getList(n, map, numbers, rst, curr, i + 1);
            curr.deleteCharAt(curr.length() - 1);
        }
    }

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.

The third problem asks us how many such numbers in a range. I use the recursion way. Basically we construct the string from the middle, if it is within the range, total number increment by 1. Recursively calculate all possibilities.

    public int strobogrammaticInRange(String low, String high) {
        int rst = 0;
        for (int i = low.length(); i <= high.length(); i++) {
            rst = getNumbers(low, high, "", i, rst);
            rst = getNumbers(low, high, "0", i, rst);
            rst = getNumbers(low, high, "1", i, rst);
            rst = getNumbers(low, high, "8", i, rst);
        }
        return rst;
    }

    private int getNumbers(String low, String high, String curr, int len, int rst) {
        if (curr.length() >= len) {
            if (curr.length() != len || (len == low.length() && curr.compareTo(low) < 0)
                || (len == high.length() && curr.compareTo(high) > 0)
                || (curr.charAt(0) == '0' && curr.length() > 1)) {
                return rst;
            }
            return rst + 1;
        }
        rst = getNumbers(low, high, "0" + curr + "0", len, rst);
        rst = getNumbers(low, high, "1" + curr + "1", len, rst);
        rst = getNumbers(low, high, "6" + curr + "9", len, rst);
        rst = getNumbers(low, high, "8" + curr + "8", len, rst);
        rst = getNumbers(low, high, "9" + curr + "6", len, rst);
        return rst;
    }