[LeetCode] 247. Strobogrammatic Number II 对称数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"].

Hint:

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

246. Strobogrammatic Number 的变形，那道题让我们判断一个数是否是对称数，而这道题让我们找出长度为n的所有的对称数。提示用递归来做，调用n-2，而不是n-1。

DFS，每次n-2，一层一层的迭代，到最后一层，n = 0 或者 n = 1 停止，backtracking加对称数字。n = 0时加"', n = 1时，加0或1或8，其它层每次加能组成对称数字对的一种组合，注意最外边一层不能是0。

Java:

public class Solution {

    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);

            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;

    }

}

Python:

class Solution:

    lookup = {'0':'0', '1':'1', '6':'9', '8':'8', '9':'6'}

    def findStrobogrammatic(self, n):

        return self.findStrobogrammaticRecu(n, n)

    def findStrobogrammaticRecu(self, n, k):

        if k == 0:

            return ['']

        elif k == 1:

            return ['0', '1', '8']

        result = []

        for num in self.findStrobogrammaticRecu(n, k - 2):

            for key, val in self.lookup.iteritems():

                if n != k or key != '0':

                    result.append(key + num + val)

        return result

C++:

class Solution {

public:

    vector<string> findStrobogrammatic(int n) {

        return find(n, n);

    }

    vector<string> find(int m, int n) {

        if (m == 0) return {""};

        if (m == 1) return {"0", "1", "8"};

        vector<string> t = find(m - 2, n), res;

        for (auto a : t) {

            if (m != n) res.push_back("0" + a + "0");

            res.push_back("1" + a + "1");

            res.push_back("6" + a + "9");

            res.push_back("8" + a + "8");

            res.push_back("9" + a + "6");

        }

        return res;

    }

};

类似题目：

[LeetCode] 246. Strobogrammatic Number 对称数

[LeetCode] 248. Strobogrammatic Number III 对称数III

All LeetCode Questions List 题目汇总