Strobogrammatic Number

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

246. Strobogrammatic Number

public boolean isStrobogrammatic(String num) {
    int n=num.length();
    //0 n-1
    //1 n-2
    for (int i = 0; i <= (n-1)/2; i++) {
        //0 1 8
        //6 9
        char c=num.charAt(i);
        if(c!='0' && c!='1' && c!='8' && c!='6' && c!='9'){
            return false;
        }
        char r=num.charAt(n-1-i);
        switch (c){
            case '0':
                if(r!='0'){
                    return false;
                }
                break;
            case '1':
                if(r!='1'){
                    return false;
                }
                break;
            case '8':
                if(r!='8'){
                    return false;
                }
                break;
            case '6':
                if(r!='9'){
                    return false;
                }
                break;
            case '9':
                if(r!='6'){
                    return false;
                }
                break;
        }
    }
    return true;
}

247. Strobogrammatic Number II

public List<String> findStrobogrammatic(int n) {
    List<String> one= Arrays.asList("0","1","8");
    List<String> two=Arrays.asList("11","69","88","96");
    if(n==1){
        return one;
    }
    if(n==2){
        return two;
    }
    List<String> res=new ArrayList<>();
    int t=n/2;
    int o=n%2;
    if(o==0){
        build(res,two,new LinkedList<>(),t);
    }else{
        for (String s : one) {
            LinkedList<Character> list=new LinkedList<>();
            list.add(s.charAt(0));
            build(res,two,list,t);
        }
    }
    return res;
}

void build(List<String> res, List<String> two, LinkedList<Character> list, int t){
    if(t==0){
        StringBuilder sb=new StringBuilder();
        for (Character c : list) {
            sb.append(c);
        }
        res.add(sb.toString());
        return;
    }
    if(t!=1){
        list.addFirst('0');
        list.addLast('0');
        build(res,two,list,t-1);
        list.removeFirst();
        list.removeLast();
    }
    for (String s : two) {
        list.addFirst(s.charAt(0));
        list.addLast(s.charAt(1));
        build(res,two,list,t-1);
        list.removeFirst();
        list.removeLast();
    }
}

248. Strobogrammatic Number III

private static final char[][] PAIRS = new char[][] {
    {'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'}, {'9', '6'}};
public int strobogrammaticInRange(String low, String high) {
    if (low == null || high == null || 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 += dfs(low, high, new char[len], 0, len - 1);
    }
    return count;
}
private int dfs(String low, String high, char[] ch, int left, int right) {
    if (left > right) {
        String s = new String(ch);
        if ((ch.length == low.length() && s.compareTo(low) < 0)
            || (ch.length == high.length() && s.compareTo(high) > 0)) {
            return 0;
        } else {
            return 1;
        }
    }
    int count = 0;
    for (char[] p : PAIRS) {
        ch[left] = p[0];
        ch[right] = p[1];
        if (ch.length != 1 && ch[0] == '0') {
            continue; //don't start with 0
        }
        if (left == right && (p[0] == '6' || p[0] == '9')) {
            continue; //don't put 6/9 at the middle of string.
        }
        count += dfs(low, high, ch, left + 1, right - 1);
    }
    return count;
}

private static final char[][] PAIRS=new char[][]{
        {'0','0'},{'1','1'},{'6','9'},{'8','8'},{'9','6'}
};

public int strobogrammaticInRange(String low, String high) {
    int res=0;
    for(int i=low.length(); i<=high.length(); i++){
        res+=dfs(low,high,new char[i],0,i-1);
    }
    return res;
}

int dfs(String low, String high, char[] chars, int left, int right){
    if(left>right){
        String s=new String(chars);
        if(s.length()==low.length() && s.compareTo(low)<0
                || s.length()==high.length() &&s.compareTo(high)>0){
            return 0;
        }
        return 1;
    }
    int count=0;
    for (char[] pair : PAIRS) {
        chars[left]=pair[0];
        chars[right]=pair[1];
        //no leading zero
        if(chars[0]=='0' && chars.length>1){
            continue;
        }
        //no middle '6' or '9'
        if(left==right && (chars[left]=='9' || chars[left]=='6')){
            continue;
        }
        count+=dfs(low,high,chars,left+1,right-1);
    }
    return count;
}