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

解法1： Recursion

承接I的思路，当数字长度大于1的时候，都需要配对存在。
要注意的是00配对只可能存在内层中，所以在递归的时候需要用一个变量记录原来n的长度。这样当不是最外层的时候就可以把0加上了。

lang: java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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<String>(Arrays.asList(""));
        if (n == 1) return new ArrayList<String>(Arrays.asList("0","1","8"));
        List<String> next = helper(n - 2, m);
        List<String> res = new ArrayList<>();
        for (String str : next) {
            if (n != m) res.add("0" + str + "0");
            res.add("1" + str + "1");
            res.add("6" + str + "9");
            res.add("8" + str + "8");
            res.add("9" + str + "6");
        }
        return res;
    }
}