Skip to content

247 Strobogrammatic Number II

Problem:

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

Solutions:

class Solution {
    public List<String> findStrobogrammatic(int n) {
        List<String> res = new LinkedList<String>();
        if (n == 0) {
            return res;
        }
        return fs(n, n);
    }
    private List<String> fs(int n, int target) {
        List<String> res = new LinkedList<String>();
        if (n == 0) {
            res.add("");
            return res;
        }
        if (n == 1) {
            res.add("0");
            res.add("1");
            res.add("8");
            return res;
        }
        List<String> tmp = fs(n - 2, target);
        for (String str:tmp) {
            res.add("1" + str + "1");
            res.add("8" + str + "8");
            res.add("6" + str + "9");
            res.add("9" + str + "6");
            if (n != target) {
                res.add("0" + str + "0");
            }
        }
        return res;
    }
}

class Solution {
    public List<String> findStrobogrammatic(int n) {
        List<String> res = new LinkedList<String>();
        process("", n, res);
        process("0", n, res);
        process("1", n, res);
        process("8", n, res);
        return res;
    }
    private void process(String cand, int n, List<String> res) {
        if (cand.length() > n) {
            return;
        }
        if (cand.length() == n) {
            if (cand.length() != 1 && cand.charAt(0) == '0') {
                return;
            }
            res.add(cand);
        }
        process("0" + cand + "0", n, res);
        process("1" + cand + "1", n, res);
        process("8" + cand + "8", n, res);
        process("6" + cand + "9", n, res);
        process("9" + cand + "6", n, res);
    }
}