[LintCode] Problem 776 - Strobogrammatic Number II

Posted on | In ,

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

No.1

Input: n = 2,

Output: [“11”,”69”,”88”,”96”]

No.2

Input: n = 1,

Output: [“0”,”1”,”8”]

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public List<String> findStrobogrammatic(int n) {
    return helper(n, n);
}

private List<String> helper(int n, int len) {
    if (n == 0)
        return new ArrayList<>(Arrays.asList(""));
    else if (n == 1)
        return new ArrayList<>(Arrays.asList("0", "1", "8"));

    List<String> result = new ArrayList<>();
    List<String> subList = helper(n - 2, len);

    for (String sub : subList) {
        if (n != len)
            result.add("0" + sub + "0");

        result.add("1" + sub + "1");
        result.add("6" + sub + "9");
        result.add("8" + sub + "8");
        result.add("9" + sub + "6");
    }

    return result;
}