753.md

753. Cracking the Safe

Solution 1 (time O(k^n), space O(k^n))

class Solution(object):
    def crackSafe(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        if n == 1:
            return "".join(str(i) for i in range(k))
        if k == 1:
            return "0" * n
        suffix_map = {}
        ans = "0" * (n-1)
        for _ in range(k ** n):
            suffix = ans[1 - n:]
            suffix_map[suffix] = suffix_map.get(suffix, k) - 1
            ans += str(suffix_map[suffix])
        return ans