247. Strobogrammatic Number II

Strobogrammatic Number II

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) {
        if (n == 0) return new ArrayList<>();
        if (n == 1) {
            List<String> result = new ArrayList<>();
            result.add("0");
            result.add("1");
            result.add("8");
            return result;
        } else if (n == 2) {
            List<String> result = new ArrayList<>();
            result.add("11");
            result.add("69");
            result.add("88");
            result.add("96");
            return result;
        } else {
            if (n % 2 == 1) {
                List<String> start = findStrobogrammatic(1);
                while (n > 1) {
                    List<String> newList = new ArrayList<>();
                    for (String s : start) {
                        newList.addAll(convert(s, n != 3));
                    }
                    start = newList;
                    n -= 2;
                }
                return start;
            } else {
                List<String> start = findStrobogrammatic(2);
                start.add("00");
                while (n > 2) {
                    List<String> newList = new ArrayList<>();
                    for (String s : start) {
                        newList.addAll(convert(s, n != 4));
                    }
                    start = newList;
                    n -= 2;
                }
                return start;
            }
        }
    }

    private List<String> convert(String s, boolean flag) {
        List<String> result = new ArrayList<>();
        result.add("8" + s + "8");
        result.add("1" + s + "1");
        result.add("6" + s + "9");
        result.add("9" + s + "6");

        if (flag) {
            result.add("0" + s + "0");
        }
        return result;
    }
}