Hard

题目描述

有一个保险箱，由密码保护。密码是一个由 n 位数字组成的序列，其中每个数字都在范围 [0, k - 1] 内。

保险箱有一种特殊的密码验证方式。当你输入一个序列时，每次输入一个数字，它都会检查你输入的最近 n 位数字。

例如，正确的密码是 “345”，你输入了 “012345”：

  • 输入 0 后，最近的 3 位数字是 “0”，不正确。
  • 输入 1 后，最近的 3 位数字是 “01”，不正确。
  • 输入 2 后，最近的 3 位数字是 “012”，不正确。
  • 输入 3 后，最近的 3 位数字是 “123”，不正确。
  • 输入 4 后，最近的 3 位数字是 “234”，不正确。
  • 输入 5 后，最近的 3 位数字是 “345”，正确，保险箱打开。

返回能在某个时刻解开保险箱的最短字符串。

示例 1:

输入: n = 1, k = 2
输出: "10"
解释: 密码是一位数字，所以输入每个数字。"01" 也能解开保险箱。

示例 2:

输入: n = 2, k = 2
输出: "01100"
解释: 对于每个可能的密码：
- "00" 从第4位数字开始输入。
- "01" 从第1位数字开始输入。
- "10" 从第3位数字开始输入。
- "11" 从第2位数字开始输入。
因此 "01100" 能解开保险箱。"10011" 和 "11001" 也能解开保险箱。

约束条件:

  • 1 <= n <= 4
  • 1 <= k <= 10
  • 1 <= k^n <= 4096

解题思路

这个问题本质上是寻找一个最短的字符串，使得所有可能的 n 位密码都作为子串出现在其中。这等价于在一个有向图中找欧拉回路。

图论建模思路：

我们可以将问题转化为图论问题：

  • 节点：所有长度为 (n-1) 的字符串，共有 k^(n-1) 个节点
  • 边：从节点 u 到节点 v 的边表示一个长度为 n 的密码，其中前 (n-1) 位是 u，后 (n-1) 位是 v
  • 目标：找到一条经过所有边恰好一次的路径（欧拉路径）

具体实现：

  1. 使用 Hierholzer 算法寻找欧拉回路
  2. 从任意节点开始（比如全0字符串）
  3. 使用DFS深度优先搜索，采用后序遍历的方式构造路径
  4. 为了避免过早陷入死胡同，我们在访问完所有出边后再将当前节点加入结果

算法优化：

  • 使用集合记录已访问的边，避免重复访问
  • 采用贪心策略，按字典序访问边，保证结果的一致性
  • 最终结果长度为 k^n + n - 1

这种方法保证能找到包含所有可能密码的最短字符串。

代码实现

class Solution {
public:
    string crackSafe(int n, int k) {
        if (n == 1) {
            string result = "";
            for (int i = 0; i < k; i++) {
                result += to_string(i);
            }
            return result;
        }
        
        unordered_set<string> visited;
        string start(n - 1, '0');
        string result;
        
        function<void(const string&)> dfs = [&](const string& node) {
            for (int i = k - 1; i >= 0; i--) {
                string edge = node + to_string(i);
                if (visited.find(edge) == visited.end()) {
                    visited.insert(edge);
                    dfs(edge.substr(1));
                    result += to_string(i);
                }
            }
        };
        
        dfs(start);
        result += start;
        return result;
    }
};

class Solution:
    def crackSafe(self, n: int, k: int) -> str:
        if n == 1:
            return ''.join(str(i) for i in range(k))
        
        visited = set()
        start = '0' * (n - 1)
        result = []
        
        def dfs(node):
            for i in range(k - 1, -1, -1):
                edge = node + str(i)
                if edge not in visited:
                    visited.add(edge)
                    dfs(edge[1:])
                    result.append(str(i))
        
        dfs(start)
        return ''.join(result) + start

public class Solution {
    public string CrackSafe(int n, int k) {
        if (n == 1) {
            var sb = new StringBuilder();
            for (int i = 0; i < k; i++) {
                sb.Append(i);
            }
            return sb.ToString();
        }
        
        var visited = new HashSet<string>();
        var start = new string('0', n - 1);
        var result = new List<char>();
        
        void Dfs(string node) {
            for (int i = k - 1; i >= 0; i--) {
                var edge = node + i;
                if (!visited.Contains(edge)) {
                    visited.Add(edge);
                    Dfs(edge.Substring(1));
                    result.Add((char)('0' + i));
                }
            }
        }
        
        Dfs(start);
        return new string(result.ToArray()) + start;
    }
}

var crackSafe = function(n, k) {
    if (n === 1) {
        let result = '';
        for (let i = 0; i < k; i++) {
            result += i;
        }
        return result;
    }
    
    const visited = new Set();
    const totalNodes = Math.pow(k, n - 1);
    let result = '0'.repeat(n);
    
    function dfs(node) {
        for (let i = 0; i < k; i++) {
            const edge = node + i;
            if (!visited.has(edge)) {
                visited.add(edge);
                const nextNode = edge.slice(1);
                dfs(nextNode);
                result += i;
            }
        }
    }
    
    dfs('0'.repeat(n - 1));
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(k^n) - 需要访问所有 k^n 个可能的密码组合
空间复杂度O(k^n) - 存储访问状态和递归调用栈的空间