LeetCode - Strobogrammatic Number III

StrobogrammaticNumberIII.java

// 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.

char[][] pairs = {{'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'}, {'9', '6'}};
int count = 0;
public int strobogrammaticInRange(String low, String high) {
    for(int len = low.length(); len <= high.length(); len++) {
        dfs(low, high, new char[len], 0, len - 1);
    }
    return count;
}

public void dfs(String low, String high, char[] c, int left, int right) {
    if(left > right) {
        String s = new String(c);
        if(isGreater(s, low) && isGreater(high, s)) count++;
        return;
    }

    for(char[] p : pairs) {
        c[left] = p[0]; 
        c[right] = p[1];
        if(c.length != 1 && c[0] == '0') continue;
        if(left < right || left == right && p[0] == p[1]) dfs(low, high, c, left + 1, right - 1);
    }
}

private boolean isGreater(String str1, String str2){
    if(str1.length() == str2.length()) return str1.compareTo(str2) >= 0;
    else return str1.length() > str2.length();
}