题目大意：让你构建一个最短字符串包含所有可能的密码。
There is a box protected by a password. The password is n digits, where each letter can be one of the first kdigits 0, 1, ..., k-1.
You can keep inputting the password, the password will automatically be matched against the last n digits entered.
For example, assuming the password is "345", I can open it when I type "012345", but I enter a total of 6 digits.
Please return any string of minimum length that is guaranteed to open the box after the entire string is inputted.
Example 1:
|
1 2 3 |
Input: n = 1, k = 2 Output: "01" Note: "10" will be accepted too. |
Example 2:
|
1 2 3 |
Input: n = 2, k = 2 Output: "00110" Note: "01100", "10011", "11001" will be accepted too. |
Note:
nwill be in the range[1, 4].kwill be in the range[1, 10].k^nwill be at most4096.
Idea: Search
Solution 1: DFS w/ backtracking
C ++
|
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 |
// Author: Huahua // Runtime: 9 ms class Solution { public: string crackSafe(int n, int k) { const int total_len = pow(k, n) + n - 1; string ans(n, '0'); unordered_set<string> visited{ans}; if (dfs(ans, total_len, n, k, visited)) return ans; return ""; } private: bool dfs(string& ans, const int total_len, const int n, const int k, unordered_set<string>& visited) { if (ans.length() == total_len) return true; string node = ans.substr(ans.length() - n + 1, n - 1); for (char c = '0'; c < '0' + k; ++c) { node.push_back(c); if (!visited.count(node)) { ans.push_back(c); visited.insert(node); if (dfs(ans, total_len, n, k, visited)) return true; visited.erase(node); ans.pop_back(); } node.pop_back(); } return false; } }; |
Solution 2: DFS w/o backtracking
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua // Running time: 13 ms class Solution { public: string crackSafe(int n, int k) { const int total_len = pow(k, n) + n - 1; string node(n - 1, '0'); string ans; unordered_set<string> visited; dfs(node, k, visited, ans); return ans + node; } private: void dfs(const string& node, const int k, unordered_set<string>& visited, string& ans) { for (char c = '0'; c < '0' + k; ++c) { string next = node + c; if (visited.count(next)) continue; visited.insert(next); dfs(next.substr(1), k, visited, ans); ans.push_back(c); } } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment