题目描述
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.
样例
Input: n = 2
Output: ["11","69","88","96"]
算法1
(DFS) $O(5^n)$
DFS 遍历从0到n - 1每一个位置和对应的尾部位置。
特殊情况:
1. 如果n为奇数中间点不可取9和6。
2. 00无效。
C++ 代码
class Solution {
public:
char singles[3] = { '0', '1', '8' }, evens[2] = { '6', '9' };
vector<string> ans;
vector<char> path;
vector<string> findStrobogrammatic(int n) {
ans.clear();
path = vector<char>(n);
dfs(0, n - 1);
return ans;
}
void dfs(int l, int r)
{
if (l > r)
{
ans.push_back(string(path.begin(), path.end()));
return;
}
for (char c : singles)
{
if (c == '0' && l == 0 && l != r) continue;
path[l] = c;
path[r] = c;
dfs(l + 1, r - 1);
}
if (l != r)
{
for (int i = 0; i < 2; i ++)
{
path[l] = evens[i];
path[r] = evens[1 - i];
dfs(l + 1, r - 1);
}
}
}
};