# [leetcode] Strobogrammatic Number && II && III

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to determine if a number is strobogrammatic. The number is represented as a string.

For example, the numbers “69”, “88”, and “818” are all strobogrammatic.

```class Solution {
public:
bool isStrobogrammatic(string num) {
vector<int> map(10, 0);
map[0] = 0;
map[1] = 1;
map[8] = 8;
map[6] = 9;
map[9] = 6;
for(int i = 0; i < num.size(); i++){
int digit = num[i] - '0';
if(digit == 0 || digit == 1 || digit == 8 || digit == 6 || digit == 9){
if(num[num.size() - 1 - i] - '0' != map[digit]){//num[num.size() - 1 - i] should - '0'
return false;
}
}
else{
return false;
}
}
return true;
}
};```

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"]`.

Hint:

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

first generate the first half of the string, since it’s symmetric.

```class Solution {
public:
char candidates[5] = {'0','1','6','8','9'};
vector<string> findStrobogrammatic(int n) {
vector<string> ans;
string thisAns;
char symmetric[3] = {'0','1','8'};
int len = n / 2;;
if(n % 2 == 1){
for(int i = 0; i < 3; i++){
thisAns.push_back(symmetric[i]);//center of the string
dfs((n + 1) / 2, thisAns, ans);
thisAns.pop_back();
}
}
else{
dfs(n / 2, thisAns, ans);
}
for(auto& word : ans){
for(int i = len - 1; i >= 0; i--){
if(word[i] == '6'){
word.push_back('9');
}else if(word[i] == '9'){
word.push_back('6');
}
else{
word.push_back(word[i]);
}
}
}
return ans;
}
void dfs(int n, string& thisAns, vector<string>& ans){
if(thisAns.size() == n){
ans.push_back(thisAns);
return ;
}
int i = 0;
if(thisAns.size() == n - 1) i = 1;//first digit should not be 0
for(; i < 5; i++){
thisAns.insert(thisAns.begin(),candidates[i]);
dfs(n, thisAns, ans);
thisAns.erase(thisAns.begin());
}
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.