LeetCod 753. Cracking the Safe题目解析

Description

There is a box protected by a password. The password is n digits, where each letter can be one of the first k digits 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:

Input: n = 1, k = 2
Output: "01"
Note: "10" will be accepted too.

Example 2:

Input: n = 2, k = 2
Output: "00110"
Note: "01100", "10011", "11001" will be accepted too.

Note:

  1. n will be in the range [1, 4].

  2. k will be in the range [1, 10].

  3. k^n will be at most 4096.

题目复述

一个密码由n位数组成,密码中每个数的范围小于k,即范围在0 – k-1,可以一直输入一个密码序列,自动将序列的后n为数作为密码输入,问最短的密码序列是什么?例如密码是"345",当输入的密码序列是"0123456"的时候可以成功解密。

题目解析

可以将该问题简化为找到一个长度最小的字符串,该字符串的子串包含所有可能的密码串。观察样例似乎有一个结论,在当前序列添加一个字符即可得到一个从未出现过的可能的密码串。如在序列"00"添加'1',即可得到"01",在"001"添加'1'可以得到"11"….

下面我们给出证明:

我们构造一个有向图,包含k^(n-1)个顶点,每个顶点有k条出边,例如对于n = 2, k = 2,就有2个顶点'0','1',每个顶点有两条边分别用'0', '1'表示,这样一个顶点加一个出边就表示一个可能的密码串,u指向v,当且仅当u+u的出边构成的字符串的后n-1个字符串和v相等。

例如对于n = 2, k = 2,构造出的有向图如下所示

image.png

有了上面的图之后我们可以发现此图中肯定存在欧拉回路(即起点和终点一样且走遍所有的遍),因为所有点的入度等于出度。得证。

接下来使用dfs找出欧拉回路即可。注意必须使用后续遍历,先序遍历会导致漏解,比如走了"00","01","10",漏了"11"。

class Solution {
public:
    set<string> wolked;
    string res;
    
    void dfs(string u, int k) {
        for(int i=0; i<k; i++) {
            string temp  = u;
            temp += '0' + i;
            if(wolked.count(temp)) continue;
            wolked.insert(temp);
            dfs(temp.substr(1), k);
            res += i + '0';
        }
    }
    
    string crackSafe(int n, int k) {
        if(k == 1) return string(n, '0');
        string start(n-1, '0');
        dfs(start, k);
        res += start;
        return res;
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注