首页 > itarticle > [lintcode] problem 776 – strobogrammatic number ii

[lintcode] problem 776 – strobogrammatic number ii

admin 11月 13, 2020 0

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

public List<String> (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;
}