Cracking the Safe LeetCode solution in Python

1
# Runtime: 121 ms (Top 27.97%) | Memory: 27.9 MB (Top 17.84%)
2
class Solution:
3
    def crackSafe(self, n: int, k: int) -> str:
4
        seen = set()
5

6
        def dfs(s, last_n):
7
            if len(seen) == (k**n):
8
                return s
9
            if (
10
                len(last_n) < n
11
            ):  # If len<n,keep adding zeros as and valid string can be returned
12
                if len(s + "0") == n:
13
                    seen.add(s + "0")
14
                ans = dfs(s + "0", last_n + "0")
15
                return ans
16
            ans = None
17
            for i in range(k):
18
                new = last_n[1:] + str(i)
19
                if new not in seen:
20
                    seen.add(new)
21
                    ans = dfs(s + str(i), new)
22
                    if ans:
23
                        return ans
24
                    seen.remove(new)
25

26
        return dfs("", "")