Original Link:
https://leetcode.com/contest/weekly-contest-64/problems/cracking-the-safe/
Solution:
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 |
class Solution { public: string crackSafe(int n, int k) { string result(n, '0'); string curr(n - 1, '0'); unordered_set<string> visited; visited.insert(result); for (;;) { bool done = true; for (int i = k - 1; i >= 0; --i) { char c = '0' + i; string s = curr + c; if (visited.find(s) == visited.end()) { curr = s.substr(1); visited.insert(std::move(s)); done = false; result += c; break; } } if (done) { break; } } return result; } }; |
Or
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 |
class Solution { public: string crackSafe(int n, int k) { const char e = '0' + k - 1; string result(n, e); string curr(n - 1, e); unordered_set<string> visited; visited.insert(result); for (;;) { bool done = true; for (int i = 0; i < k; ++i) { char c = '0' + i; string s = curr + c; if (visited.find(s) == visited.end()) { curr = s.substr(1); visited.insert(std::move(s)); done = false; result += c; break; } } if (done) { break; } } return result; } }; |