Cracking the Safe — LeetCode 753 Python Solution

The problem

There is a safe protected by a password. The password is a sequence of n digits where each digit can be in the range [0, k - 1].

Example

Input

n = 1, k = 2

Output

"10"

Explanation

The password is a single digit, so enter each digit. "01" would also unlock the safe.

Python solution

class Solution:
    def crackSafe(self, n: int, k: int) -> str:
        def dfs(u):
            for x in range(k):
                e = u * 10 + x
                if e not in vis:
                    vis.add(e)
                    v = e % mod
                    dfs(v)
                    ans.append(str(x))

        mod = 10 ** (n - 1)
        vis = set()
        ans = []
        dfs(0)
        ans.append("0" * (n - 1))
        return "".join(ans)

Complexity

Pattern: Depth-First Search

Follow one path to its end before trying the next — the default way to explore a graph. LeetCode 753. Cracking the Safe is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Depth-First Search and Graph.

The depth-first search guide has the Python template for the pattern and the 366 LeetCode problems that use it.

Related problems