Leetcode #247. Strobogrammatic Number II

[yokostan]

class Solution {
    public List<String> findStrobogrammatic(int n) {
        List<String> one = Arrays.asList("0", "1", "8"), two = Arrays.asList(""), res = two;
        if (n % 2 == 1) res = one;

        for (int i = (n % 2) + 2; i <= n; i += 2) {
            List<String> newList = new ArrayList<>();
            for (String str : res) {
                if (i != n) newList.add("0" + str + "0");
                newList.add("1" + str + "1");
                newList.add("8" + str + "8");
                newList.add("6" + str + "9");
                newList.add("9" + str + "6");
            }
            res = newList;
        }

        return res;
    }
}

Recursive:

class Solution {
    public List<String> findStrobogrammatic(int n) {
        return helper(n, n);
    }

    private List<String> helper(int i, int n) {
        if (i == 0) return new ArrayList<String>(Arrays.asList(""));
        if (i == 1) return new ArrayList<String>(Arrays.asList("0", "1", "8"));

        List<String> list = helper(i - 2, n);
        List<String> res = new ArrayList<String>();

        for (int k = 0; k < list.size(); k++) {
            String s = list.get(k);
            if (i != n) res.add("0" + s + "0");
            res.add("1" + s + "1");
            res.add("8" + s + "8");
            res.add("6" + s + "9");
            res.add("9" + s + "6");
        }

        return res;
    }
}