753. Cracking the Safe

753. Cracking the Safe

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.

----------------
题意是找一个最短的string，这个string得包含所有n长度的排列组合。最优的解是2个排列组合之间只相差一位，如 1234 -> 2345, *234 -> 234*. 解法是把234看作一个结点，12345为这个结点的边，把所有边都遍历一次就可以了
Eulerian path的定义https://en.wikipedia.org/wiki/Eulerian_path
用Hierholzer's algorithm来求path

O(k * k^n) time, Hierholzer's algorithm本来 是O(k^n), 但是以下实现方式每次都对k个边做检查来寻找未走过的边，所以有额外的k消耗
ToDo

class Solution {
    public String crackSafe(int n, int k) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append("0");
        }
        
        Set<String> visited = new HashSet<>();
        visited.add(sb.toString());
        dfs(sb, visited, k, n);
        return sb.toString();
    }
    
    private void dfs(StringBuilder sb, Set<String> visited, int k, int n) {
        String node = sb.substring(sb.length() - n + 1);
        for (int i = k - 1; i >= 0; i--) {
            String s = node + Integer.toString(i);
            if (!visited.contains(s)) {
                visited.add(s);
                sb.append(Integer.toString(i));
                dfs(sb, visited, k, n);
            }
        }
    }
}