Python Eular path, 62 ms.


  • 0
    Y
    class Solution(object):
        def crackSafe(self, n, k):
            """
            :type n: int
            :type k: int
            :rtype: str
            """
            if n==1:
                return "".join(map(str,range(k)))
            neighbors = {}
            for i in xrange(k**(n-1)):
                digits = ['0']*(n-1)
                for j in xrange(n-1):
                    digits[-1-j] = str(i%k)
                    i /= k
                num = "".join(digits)
                neighbors[num] = []
                for j in xrange(k):
                    neighbors[num].append(num[1:]+str(j))
            stack,ans = ['0'*(n-1)],[]
            while len(stack)>0:
                if len(neighbors[stack[-1]])==0:
                    word = stack.pop()
                    ans.append(word[-1])
                else:
                    neighb = neighbors[stack[-1]].pop()
                    stack.append(neighb)
            ans.append('0'*(n-2))
            return "".join(ans)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.