[LeetCode] Cracking the Safe

Problem: There is a box protected by a password. The password is a sequence of n digits where each digit can be one of the first k digits 0, 1, ..., k-1.

While entering a password, the last n digits entered will automatically be matched against the correct password.

For example, assuming the correct password is "345", if you type "012345", the box will open because the correct password matches the suffix of the entered password.

Return any password of minimum length that is guaranteed to open the box at some point of entering it.

Example:

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

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

Approach: We can think of this problem as the problem of finding an Euler Path (a path visiting every edge exactly once) on the graph of  k ^ (n - 1) nodes with each node having k edges. Given that every node has exactly k incoming and k outgoing edges, there is an Euler path exist in the graph. For example:

k = 3 and n = 2, the nodes are 00, 01, 02, 03, ..., 22 and each node has 3 edges 0, 1 and 2.

We can modify the DFS to get the Euler path in the graph. First we record the visited edges (as we need to visit every edge once only) instead of visited nodes and also we first traverse the node's children and then come back to node. Why?

Take an example of k = 2 and n = 2. If we go by normal DFS, we won't be able to visit all the edges. We will visit 0->0, 0->1, 1->0 but than we will stuck at the node 0 and we will never be able to visit the node 11. That's why we need to process it in post order fashion.

Implementation in C#:

    public string CrackSafe(int n, int k) 

    {

        if (n == 1 && k == 1)

        {

            return "0";

        }

        HashSet<string> visited = new HashSet<string>();

        string result = string.Empty;

        string start = string.Empty;

        for (int i = 0; i < n - 1; ++i)

        {

            start += '0';

        }        

        this.CrackSafeDFS(start, k, visited, ref result);

        result += start;

        return result;

    }

    

    private void CrackSafeDFS(string startNode, int k, HashSet<string> visited, ref string result)

    {

        for (int i = 0; i < k; ++i)

        {

            string next = $"{startNode}{i}";

            if (!visited.Contains(next))

            {

                visited.Add(next); // storing edge

                this.CrackSafeDFS(next.Substring(1), k, visited, ref result);

                // post order 

                result += i.ToString();

            }

        }

    }

Complexity: O(n * k ^ n)