386. Lexicographical Numbers

Problem

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.

Problem Summary

Given an integer n, return the lexicographical order from 1 to n. For example, given n =13, return [1,10,11,12,13,2,3,4,5,6,7,8,9].

Please optimize the time complexity and space complexity of the algorithm as much as possible. The input data n is less than or equal to 5,000,000.

Solution Approach

• Given a number n, sort the n numbers from 1 to n in lexicographical order.
• A brute-force DFS solution is sufficient.

Code

package leetcode

func lexicalOrder(n int) []int {
	res := make([]int, 0, n)
	dfs386(1, n, &res)
	return res
}

func dfs386(x, n int, res *[]int) {
	limit := (x + 10) / 10 * 10
	for x <= n && x < limit {
		*res = append(*res, x)
		if x*10 <= n {
			dfs386(x*10, n, res)
		}
		x++
	}
}