Leetcode - Strobogrammatic Number III

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.
[分析]
思路1：比较容易想到的思路，利用题II的思路构造出low.length 和high.length之间的所有strobogrammatic number, 然后计数在low-high范围内的那些数字个数。
思路2：参考https://leetcode.com/discuss/50624/clean-and-easy-understanding-java-solution 在构造过程中判断并计数，且构造方式是从两边往中间，而思路1是从中间忘两边。在leetcode的运行时间优于思路1
思路3：受思路2启发，改造思路1，也在构造过程中判断，修改过程各种bug调试好久，而且运行时间远高于思路1和思路2，无言~

public class Solution {
    // Method 2: ref
    Map<Character, Character> map = new HashMap<>();
    {
        map.put('1', '1');
        map.put('8', '8');
        map.put('6', '9');
        map.put('9', '6');
        map.put('0', '0');
    }
    String low = "", high = "";
    public int strobogrammaticInRange(String low, String high) {
        this.low = low;
        this.high = high;
        int result = 0;
        for(int n = low.length(); n <= high.length(); n++){
            int[] count = new int[1];
            strobogrammaticInRange(new char[n], count, 0, n-1);
            result += count[0];
        }
        return result;
    }
    private void strobogrammaticInRange(char[] arr, int[] count, int lo, int hi){
        if(lo > hi){
            String s = new String(arr);
            if((arr[0] != '0' || arr.length == 1) && compare(low, s) && compare(s, high)){
                count[0]++;
            }
            return;
        }
        for(Character c: map.keySet()){
            arr[lo] = c;
            arr[hi] = map.get(c);
            if((lo == hi && c == map.get(c)) || lo < hi)
                strobogrammaticInRange(arr, count, lo+1, hi-1);
        }
    }
    private boolean compare(String a, String b){
        if(a.length() != b.length())
            return a.length() < b.length();
        int i = 0;
        while(i < a.length() &&a.charAt(i) == b.charAt(i))
            i++;
        return i == a.length() ? true: a.charAt(i) <= b.charAt(i);
    }
    
    // Method 1
    public int strobogrammaticInRange1(String low, String high) {
        int count = 0;
        int minLen = low.length(), maxLen = high.length();
        for (int n = minLen; n <= maxLen; n++) {
            List<String> candidates = recur(n, n);
            if (n == minLen || n == maxLen) {
                for (String cand : candidates) {
                    if (isLess(low, cand) && isLess(cand, high))
                        count++;
                }
            } else {
                count += candidates.size();
            }
        }
        return count;
    }
    public List<String> recur(int k, int n) {
        List<String> result = new ArrayList<String>();
        if (k <= 0) {
            result.add("");
            return result;
        }
        if (k == 1) {
            result.add("0");
            result.add("1");
            result.add("8");
            return result;
        }
        List<String> subResult = recur(k - 2, n);
        for (String substr : subResult) {
            if (k < n) result.add('0' + substr + '0');
            result.add('1' + substr + '1');
            result.add('8' + substr + '8');
            result.add('6' + substr + '9');
            result.add('9' + substr + '6');
        }
        return result;
    }
    private boolean isLess(String a, String b) {
        if (a.length() != b.length())
            return a.length() <= b.length() ? true : false;
        int i = 0;
        while (i < a.length() && a.charAt(i) == b.charAt(i))
            i++;
        return i == a.length() ? true : a.charAt(i) <= b.charAt(i);
    }
}

public class Solution {
    // Method 3
    String low = null, high = null;
    public int strobogrammaticInRange(String low, String high) {
        this.low = low;
        this.high = high;
        int count = 0;
        int minLen = low.length(), maxLen = high.length();
        for (int n = minLen; n <= maxLen; n++) {
            List<String> candidates = recur(n, n, minLen, maxLen);
            count += candidates.size();
        }
        return count;
    }
    Map<Character, Character> map = new HashMap<>();
    {
        map.put('1', '1');
        map.put('8', '8');
        map.put('6', '9');
        map.put('9', '6');
    }
    public List<String> recur(int k, int n, int minLen, int maxLen) {
        List<String> result = new ArrayList<String>();
        if (k <= 0) {
            result.add("");
            return result;
        }
        if (k == 1) {
            if (k < n || isLessOrEqual(this.low, "0") && isLessOrEqual("0", this.high))
                result.add("0");
            if (k < n || isLessOrEqual(this.low, "1") && isLessOrEqual("1", this.high))
                result.add("1");
            if (k < n || isLessOrEqual(this.low, "8") && isLessOrEqual("8", this.high))
                result.add("8");
            return result;
        }
        List<String> subResult = recur(k - 2, n, minLen, maxLen);
        for (String substr : subResult) {
            if (k < n) result.add('0' + substr + '0');
            for (Character c : map.keySet()) {
                String cand = c + substr + map.get(c);
                if (k == n) {
                    if ((minLen < n && n < maxLen) || isLessOrEqual(this.low, cand) && isLessOrEqual(cand, this.high))
                        result.add(cand);
                } else {
                    result.add(cand);
                }
            }
        }
        return result;
    }
    
    private boolean isLessOrEqual(String a, String b) {
        if (a.length() != b.length())
            return a.length() <= b.length() ? true : false;
        int i = 0;
        while (i < a.length() && a.charAt(i) == b.charAt(i))
            i++;
        return i == a.length() ? true : a.charAt(i) <= b.charAt(i);
    }
}