247. 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:

Method 1: Recursive

Recursively add valid pairs to the left and right of current elements.

If we only need elements of length 0, we return "".

If we only need elements of length 1, we return "0", "1", and "8".

Notice if the targetLen we need is not equal to the totalLen, we can add "0" to left and right.



Code:

public class Solution {
    public List<String> findStrobogrammatic(int n) {
        return helper(n, n);
    }
    public List<String> helper(int targetLen, int totalLen) {
        if (targetLen == 0) {
            return new ArrayList(Arrays.asList(""));
        }
        if (targetLen == 1) {
            return new ArrayList(Arrays.asList("1", "8", "0"));
        }
        List<String> sub = helper(targetLen - 2, totalLen);
        List<String> result = new ArrayList<>();
        for (String str : sub) {
            if (targetLen != totalLen) {
                result.add("0" + str + "0");
            }
            result.add("1" + str + "1");
            result.add("6" + str + "9");
            result.add("9" + str + "6");
            result.add("8" + str + "8");
        }
        return result;
    }
}

Method 2: Iterative

We first check if n is odd or even.

If it is even, we start with an empty string "".

If it is odd, we start with string "1", "0", and "8".

Use a loop to decrease n by 2 each time and add a pair of numbers to all the elements in the result list.

If the leftover numbers we can add are more than 3, we can add "0" to the left and right.



Code:

public class Solution {
    public List<String> findStrobogrammatic(int n) {
        List<String> result = new ArrayList<>();
        if (n % 2 == 0) {
            result.add("");
        }
        else {
            result.add("1");
            result.add("8");
            result.add("0");
        }
        while (n >= 2) {
            List<String> tmp = result;
            result = new ArrayList<String>();
            for (String str : tmp) {
                if (n > 3) {
                    result.add("0" + str + "0");
                }
                result.add("1" + str + "1");
                result.add("8" + str + "8");
                result.add("6" + str + "9");
                result.add("9" + str + "6");
            }
            n -= 2;
        }
        return result;
    }
}