247. Strobogrammatic Number II

Problem:

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.

Example:

Input:  n = 2
Output: ["11","69","88","96"]

Analysis:

找规律： 

n = 0: ""

n = 1: 0, 1, 8

n = 2: 88, 69, 11, 96

n = 3: 808, 609, 101, 906， 818, 619, 111, 916, 888, 689, 181, 986

可以发现n是在n-2的基础上开头和结尾都同时加上strobogrammatic对。如果n是要求的长

度那么还需要排除0.

Solution:

这里第二个parameter的目的就是为了排除leading and tailing zeroes. 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

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