Leetcode: Lexicographical Numbers

Given an integer n, return 1 – n in lexicographical order.



Similar Problems:


Given an integer n, return 1 – n in lexicographical order.

For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].

Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


## Blog link: https://code.dennyzhang.com/lexicographical-numbers
## Basic Ideas: DFS
##
##  When to push? How to find the neighbors?
##
## Complexity: Time O(k), Space O(d)
##             k = size of final result
##             d = digits of n
class Solution:
    def lexicalOrder(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        res, stack = [], []
        v = 1
        while v <= n:
            res.append(v)
            stack.append(v)
            v = v*10

        while len(stack) != 0:
            v = stack.pop()+1
            while v <= n:
                res.append(v)
                if v % 10 != 9:
                    stack.append(v)
                v = v*10
        return res
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.