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.
Example:
Input: n = 2
Output: [“11″,”69″,”88″,”96”]Hints:
Try to use recursion and notice that it should recurse with n – 2 instead of n – 1.
Depth First Search Algorithm
A valid Strobogrammatic contains only digits from [0, 1, 6, 8, 9]. We can use Depth First Search Algorithm to bruteforce all possibilities with given size N, then use the routine from here to check if it is a valid Strobogrammatic number. Special case is zero which is only valid when length is 1.
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 39 40 41 42 43 | class Solution { public: vector<string> findStrobogrammatic(int n) { dfs(n, ""); return res; } private: vector<string> res; void dfs(int n, string cur) { if (n == 0) { if (isStrobogrammatic(cur)) { if ((cur.size() > 1) && (cur[0] == '0')) return; res.push_back(cur); } return; } for (const auto &s: {"0", "1", "6", "8", "9"}) { dfs(n - 1, cur + s); } } bool isStrobogrammatic(string num) { int len = num.size(); for (int i = 0; i < len; ++ i) { switch (num[i] - 48) { case 2: case 3: case 4: case 5: case 7: return false; case 6: if ('9' != num[len - 1 - i]) return false; break; case 9: if ('6' != num[len - 1 - i]) return false; break; case 1: case 8: case 0: if (num[i] != num[len - 1 - i]) return false; break; } } return true; } }; </string> |
class Solution {
public:
vector<string> findStrobogrammatic(int n) {
dfs(n, "");
return res;
}
private:
vector<string> res;
void dfs(int n, string cur) {
if (n == 0) {
if (isStrobogrammatic(cur)) {
if ((cur.size() > 1) && (cur[0] == '0')) return;
res.push_back(cur);
}
return;
}
for (const auto &s: {"0", "1", "6", "8", "9"}) {
dfs(n - 1, cur + s);
}
}
bool isStrobogrammatic(string num) {
int len = num.size();
for (int i = 0; i < len; ++ i) {
switch (num[i] - 48) {
case 2:
case 3:
case 4:
case 5:
case 7: return false;
case 6: if ('9' != num[len - 1 - i]) return false; break;
case 9: if ('6' != num[len - 1 - i]) return false; break;
case 1:
case 8:
case 0: if (num[i] != num[len - 1 - i]) return false; break;
}
}
return true;
}
};
</string>This is not ideal, as we have to go through O(N) to check if the final string is valid Strobogrammatic, the runtime complexity is O(N*5N) – which is exponetial.
Improved Depth First Search Algorithm
We can get rid of the Strobogrammatic checking by only placing the valid digits. First we define a [left, right] range where the next valid digits are. If we place a digit at [left] position we have to place its corresponding digit at [right]. This will reduce the complexity to O(5N/2)
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 | class Solution { public: vector<string> findStrobogrammatic(int n) { dfs(0, n - 1, string(n, ' ')); return res; } private: vector<string> res; void dfs(int left, int right, string cur) { if (left > right) { if ((cur.size() > 1) && (cur[0] == '0')) return; res.push_back(cur); return; } for (const auto &s: {'0', '1', '8'}) { cur[left] = s; cur[right] = s; dfs(left + 1, right - 1, cur); } if (left < right) { for (const auto &s: {'6', '9'}) { cur[left] = s; cur[right] = s == '6' ? '9' : '6'; dfs(left + 1, right - 1, cur); } } } }; |
class Solution {
public:
vector<string> findStrobogrammatic(int n) {
dfs(0, n - 1, string(n, ' '));
return res;
}
private:
vector<string> res;
void dfs(int left, int right, string cur) {
if (left > right) {
if ((cur.size() > 1) && (cur[0] == '0')) return;
res.push_back(cur);
return;
}
for (const auto &s: {'0', '1', '8'}) {
cur[left] = s;
cur[right] = s;
dfs(left + 1, right - 1, cur);
}
if (left < right) {
for (const auto &s: {'6', '9'}) {
cur[left] = s;
cur[right] = s == '6' ? '9' : '6';
dfs(left + 1, right - 1, cur);
}
}
}
};Both algorithms have O(N) space complexity due to implicit stack usage from Recursion.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Depth First Search Algorithm to Compute the Diameter of N-Ary Tree
Next Post: Algorithm to Shuffle String in Python3 According to Index
