Strobogrammatic Number II

Description

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

Hint

Try to use recursion and notice that it should recurse with n - 2 instead of n - 1.

Train of Thought

首先要看奇偶, 如果是奇数, 中间的值是单独列出来的, 其他的值都是成对增加的

重点思想: 从中间往两边扩散增加

Code

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> res = new ArrayList<String>();

for (int i = 0; i < list.size(); i++) {
    String s = list.get(i);
    //judge if it is the start and end
    if (n != m) res.add("0" + s + "0");

    res.add("1" + s + "1");
    res.add("6" + s + "9");
    res.add("8" + s + "8");
    res.add("9" + s + "6");
}

return res;

}

Complexity

Complexity of string concatenation is O(size of string) in this case