Strobogrammatic Number II

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

n = 0: none
n = 1: 0, 1, 8
n = 2: 11, 69, 88, 96
n = 3: 101, 609, 808, 906, 111, 619, 818, 916, 181, 689, 888, 986
n = 4: 1001, 6009, 8008, 9006, 1111, 6119, 8118, 9116, 1691, 6699, 8698, 9696, 1881, 6889, 8888, 9886, 1961, 6969, 8968, 9966

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

public class Solution {
    public List<String> findStrobogrammatic(int n) {
        List<String> one = Arrays.asList("0", "1", "8");
        List<String> two = Arrays.asList("");
        
        List<String> result = two;
        
        if (n % 2 == 1) {
            result = one;
        }
        
        for (int i = (n % 2) + 2; i <= n; i += 2) {
            List<String> newList = new ArrayList<>();
            
            for (String str : result) {
                if (i != n) {
                    newList.add("0" + str + "0");
                }
                
                newList.add("1" + str + "1");
                newList.add("6" + str + "9");
                newList.add("8" + str + "8");
                newList.add("9" + str + "6");
            }
            
            result = newList;
        }
        
        return result;
    }
}

Hope this helps,
Michael