386.Lexicographical Numbers

Tags: [DFS]

Link: https://leetcode.com/problems/lexicographical-numbers/?tab=Description

Given an integern, return 1 -nin 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.

Solution: DFS

class Solution(object):
    def lexicalOrder(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        if n <= 0:
            raise ValueError('the input is invalid')

        result = []
        for prefix in xrange(1, 9 + 1):
            self.dfs(prefix, n, result)

        return result

    def dfs(self, prefix, n, result):
        # base case
        if prefix > n:
            return

        result.append(prefix)
        for increment in xrange(0, 10):
            if prefix * 10 + increment > n:
                break
            self.dfs(prefix * 10 + increment, n, result)

Revelation:

• Think about this is a forest (multiple trees), we start from the prefix '1', then to do DFS (recursion) to go deeper and deeper, next level starts from '10', and the level under the next starts from '100'..., and in each level recursion we add 1, 2, 3, ... 9 to the (prefix * 10) to build the new prefix for the next level recursion.

Note:

• Time complexity = O(n), n is the given number. Finally we build an array which contains n numbers, and we append the number into the array one by one, so the time complexity is O(n).

Time Limited Exceeded

class Solution(object):
    def lexicalOrder(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        if n <= 0:
            raise ValueError('the input is invalid')

        return sorted(range(1, n + 1), cmp=self.compare_num_lexicographical)

    def compare_num_lexicographical(self, num1, num2):
        num1_s = str(num1)
        num2_s = str(num2)
        if num1_s == num2_s:
            return 0
        elif num1_s < num2_s:
            return -1
        else:
            return 1

Note:

• Time complexity = O(nlgn), n is the given number.