248. Strobogrammatic Number III

// LeetCode URL: https://leetcode.com/problems/strobogrammatic-number-iii/

/**
 * Construct strobogrammatic numbers from low.length() to high.length()
 *
 * Time Complexity: O(l Sum H (5 ^ (i/2))) = O(5^(H/2) - 5^(L/2))
 *
 * Space Complexity: O(H)
 *
 * L = length of low string. H = length of high string.
 */
class Solution {
    private static final char[][] PAIRS = new char[][] { { '0', '0' }, { '1', '1' }, { '8', '8' }, { '6', '9' },
            { '9', '6' } };

    public int strobogrammaticInRange(String low, String high) {
        if (low == null || high == null) {
            return 0;
        }

        // Below section of code removes the leading zeros from low and high input
        // strings. Only write this is this case can happen.
        // ---------------------------------------------------------------------
        int i = 0;
        while (i < low.length() && low.charAt(i) == '0') {
            i++;
        }
        if (i == low.length()) {
            low = "0";
        } else {
            low = low.substring(i);
        }
        i = 0;
        while (i < high.length() && high.charAt(i) == '0') {
            i++;
        }
        if (i == high.length()) {
            high = "0";
        } else {
            high = high.substring(i);
        }
        // ---------------------------------------------------------------------

        if (low.length() > high.length() || (low.length() == high.length() && low.compareTo(high) > 0)) {
            return 0;
        }

        int count = 0;
        for (int len = low.length(); len <= high.length(); len++) {
            count += helper(low, high, new char[len], 0, len - 1);
        }
        return count;
    }

    private int helper(String low, String high, char[] chArr, int left, int right) {
        if (left > right) {
            String s = new String(chArr);
            if ((s.length() == low.length() && s.compareTo(low) < 0)
                    || (s.length() == high.length() && s.compareTo(high) > 0)) {
                return 0;
            } else {
                return 1;
            }
        }
        int cnt = 0;
        for (char[] p : PAIRS) {
            if (chArr.length > 1 && left == 0 && p[0] == '0') {
                continue;
            }
            if (left == right && p[0] != p[1]) {
                continue;
            }
            chArr[left] = p[0];
            chArr[right] = p[1];
            cnt += helper(low, high, chArr, left + 1, right - 1);
        }
        return cnt;
    }
}