力扣（LeetCode）247. 中心对称数 II（2022.09.04）

给定一个整数 n ，返回所有长度为 n 的 中心对称数 。你可以以 任何顺序 返回答案。

中心对称数 是一个数字在旋转了 180 度之后看起来依旧相同的数字（或者上下颠倒地看）。

示例 1:

输入：n = 2
输出：[“11”,“69”,“88”,“96”]

示例 2:

输入：n = 1
输出：[“0”,“1”,“8”]

提示：

1 <= n <= 14

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/strobogrammatic-number-ii

方法一：回溯法

C++提交内容：

class Solution {
private:
    unordered_map<char, char> m = {
            {'0', '0'},
            {'1', '1'},
            {'6', '9'},
            {'8', '8'},
            {'9', '6'}
    };
    vector<string> ans;
public:

    void dfs(string s, int n) {
        if (s.length() == n) {
            if ((s[0] != '0' && n > 1) || n == 1) ans.push_back(s);
            return;
        }
        unordered_map<char, char>::iterator iter;
        for (iter = m.begin(); iter != m.end(); iter++) {
            s = iter->first + s + iter->second;
            dfs(s, n);
            s = s.substr(1, s.length() - 2);
        }
    }

    vector<string> findStrobogrammatic(int n) {
        if (n % 2 == 0) {
            dfs("", n);
        }
        else {
            dfs("0", n);
            dfs("1", n);
            dfs("8", n);
        }
        return ans;
    }
};
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
26
27
28
29
30
31
32
33
34
35
36
37