Cracking the Safe Python Solution with Tests

lcpy gen -n 753   # by problem number
lcpy gen -s cracking_the_safe   # by problem name

Input: n = 1, k = 2
Output: "10"
Explanation: The password is a single digit, so enter each digit. "01" would also unlock the safe.

Input: n = 2, k = 2
Output: "01100"
Explanation: For each possible password:
- "00" is typed in starting from the 4th digit.
- "01" is typed in starting from the 1st digit.
- "10" is typed in starting from the 3rd digit.
- "11" is typed in starting from the 2nd digit.
Thus "01100" will unlock the safe. "10011", and "11001" would also unlock the safe.

class Solution:
    # Time: O(k^n) - each of the k^n edges is visited exactly once
    # Space: O(k^n) - visited set plus the Eulerian path stack
    def crack_safe(self, n: int, k: int) -> str:
        if n == 1:
            return "".join(str(d) for d in range(k - 1, -1, -1))

        start = "0" * (n - 1)
        seen: set[str] = set()
        digits: list[str] = []

        def dfs(node: str) -> None:
            for d in range(k):
                edge = node + str(d)
                if edge not in seen:
                    seen.add(edge)
                    dfs(edge[1:])
                    digits.append(str(d))

        dfs(start)
        return "".join(digits) + start