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"].

Solution

public class Solution {
    public List<String> findStrobogrammatic(int n) {
        // 1 6 9 8 0
        List<String> ans = new ArrayList<String>();
        back(ans, new ArrayList<Integer>(), n, n);
        return ans;
    }

    public int[] candidate = {1, 6, 8, 9}; // and 0
    public int[] self = {0, 1, 8};

    public int getStro(int i) {
        if(i == 0) return 0;
        if(i == 1) return 1;
        if(i == 6) return 9;
        if(i == 8) return 8;
        if(i == 9) return 6;
        return 0;
    }

    public void back(List<String> ans, List<Integer> path, int remain, int total) {

        if(remain == 0 || remain == 1) {
            StringBuilder sb1 = new StringBuilder();
            StringBuilder sb2 = new StringBuilder();
            for(Integer i: path) {
                sb1.append(i);
                sb2.append(getStro(i));
            }

            String head = sb1.toString();
            String tail = sb2.reverse().toString();
            if(remain == 1) {
                for(int can: self) ans.add(head + can + tail);
            } else {
                ans.add(head + tail);    
            }
        } else {
            if(remain != total) {
                path.add(0);
                back(ans, path, remain - 2, total);
                path.remove(path.size() - 1);
            }
            for(int can: candidate) {
                path.add(can);
                back(ans, path, remain - 2, total);
                path.remove(path.size() - 1);
            }

        }
    }
}