753. Cracking the Safe

https://leetcode.com/problems/cracking-the-safe/description/

让生成一个最短的字符串能匹配任意的n位(每位的值范围为[0,k - 1])的字符串密码。最短的字符串肯定是重复利用了当前字符串末尾 k - 1位再加上新生成的一位拼出一种可能的密码，比如n = 2, k = 2当前是00, 重复利用末尾的0和下一个可能的字符1拼，001就能cover 00和01两种情况了。一共有n^k个可能密码，因此DFS遍历所有可能性并当前path包含所有的可能密码==n^k时即是一种结果。可以证明这样的解一定存在且只需遍历一次就能找到，不过我不会证。

思路参考了花花的。

/*
 * @lc app=leetcode id=753 lang=cpp
 *
 * [753] Cracking the Safe
 */
class Solution {
public:
    bool dfs(string &res, const int n, const int k, unordered_set<string> &path) {
        if (path.size() == pow(k, n)) return true;
        string cur = res.substr(res.length() - n + 1, n - 1);
        for (char c = '0'; c < '0' + k; ++c) {
            cur.push_back(c);
            if (!path.count(cur)) {
                res.push_back(c);
                path.insert(cur);
                if (dfs(res, n, k, path)) return true;
                path.erase(cur);
                res.pop_back();
            }
        }
        return false;
    }
    string crackSafe(int n, int k) {
        string res(n, '0');
        unordered_set<string> path{res};
        dfs(res, n, k, path);
        return res;
    }
};