247. Strobogrammatic Number II
Given an integer n, return all the strobogrammatic numbers that are of length n. You may return the answer in any order.
A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
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
38
| class Solution {
vector<string> res;
unordered_map<char, char> strobogrammatic {
{'0','0'},{'1','1'},{'6','9'},{'8','8'},{'9','6'}
};
string makeString(string& ans, string additional) {
string res = ans + additional;
for(int i = ans.length() - 1; i >= 0; i--) {
res += strobogrammatic[ans[i]];
}
return res;
}
void backTracking(string& ans, int n) {
if(ans.length() == (n/2)) {
if(n&1) {
res.push_back(makeString(ans,"0"));
res.push_back(makeString(ans,"1"));
res.push_back(makeString(ans,"8"));
} else {
res.push_back(makeString(ans,""));
}
return;
}
for(auto [key, _]: strobogrammatic) {
if(ans.length() == 0 and key == '0') continue;
ans += key;
backTracking(ans, n);
ans.pop_back();
}
return;
}
public:
vector<string> findStrobogrammatic(int n) {
string tmp = "";
backTracking(tmp, n);
return res;
}
};
|
