Python Iterative DFS solution


  • 0
    P

    Idea is to find the next one. The pattern is like a tree. e.g. 1's children is 10, 11, 12, ..., 19. 10's children is 101, 102, ..., 109. If any children is larger than n, then prune it away from this tree.
    Then, using pre-order traversal on this tree solved the problem.
    Optimization is to 1) prune the useless edges as soon as possible. 2) calculate children by multiplication.

    Time: O(N) Space: O( 10 * log_10(N) )

    class Solution(object):
        def lexicalOrder(self, n):
            """
            Iterative DFS.
            O(N)
            """
            if n <= 0:
                return []
            stack = range(min(n, 9), 0, -1)
            ret = []
            while len(stack) > 0:
                cur = stack.pop()
                ret.append(cur)
                base = cur * 10
                if base > n:
                    continue
                for i in xrange(9, -1, -1): # 9 to 0
                    t = base + i
                    if t <= n:
                        stack.append(t)
            return ret
    

Log in to reply
 

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