Cracking the Safe Solution in Python

Explore More Solutions:

Problem Description

Imagine you’re a master thief (not that we condone such behavior, of course) trying to crack a safe that has a combination lock. The safe requires a password made up of digits, and you have a limited number of digits (k) to choose from. The catch? The password must be of a certain length (n), and you want to ensure that every possible combination of the digits is included in your password.

So, if you think you can just randomly guess the password, think again! You need to be strategic about it. It’s like trying to guess your friend’s Netflix password, but instead of just a few letters, you have to consider all possible combinations of numbers. Good luck with that!

Code Solution


class Solution:
    def crackSafe(self, n: int, k: int) -> str:
        passwordSize = k**n
        path = '0' * n
        seen = set()
        seen.add(path)

        def dfs(path: str) -> str:
            if len(seen) == passwordSize:
                return path

            for c in map(str, range(k)):
                node = path[-n + 1:] + c if n > 1 else c
                if node not in seen:
                    seen.add(node)
                    res = dfs(path + c)
                    if res:
                        return res
                    seen.remove(node)

        return dfs(path)

Approach Explanation

The code uses a depth-first search (DFS) approach to explore all possible combinations of the password. It starts with a base path of ‘0’ repeated n times and keeps track of the combinations it has already seen. The function recursively builds the password by appending digits and checking if all combinations have been covered. If it finds a valid combination, it returns the complete password.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(kⁿ)
Space Complexity	O(kⁿ)

Real-World Example

Think of this problem like trying to unlock a vending machine that only accepts a specific sequence of button presses. You have a limited number of buttons (digits) and need to press them in a way that covers every possible combination to ensure you can get that delicious snack you’ve been craving. Just like the thief cracking the safe, you need to be methodical and strategic in your approach!