Sponsored
Sponsored
The idea is to perform a depth-first search (DFS) to generate numbers in lexicographical order. Starting from the number 1, we explore all numbers that can be formed by appending digits from 0 to 9 as long as the generated number is less than or equal to n. If we reach a number greater than n, backtrack and explore the next number at the same level and repeat the process.
Time Complexity: O(n), Space Complexity: O(1) (excluding the output array).
1import java.util.ArrayList;
2import java.util.List;
3
4public class Lexical
5OrderDFS {
6 private void dfs(int current, int n, List<Integer> result) {
7 if (current > n) return;
8 result.add(current);
9 for (int i = 0; i <= 9; ++i) {
10 if (current * 10 + i > n) return;
11 dfs(current * 10 + i, n, result);
12 }
13 }
14
15 public List<Integer> lexicalOrder(int n) {
16 List<Integer> result = new ArrayList<>();
17 for (int i = 1; i < 10; ++i) {
18 dfs(i, n, result);
19 }
20 return result;
21 }
22
23 public static void main(String[] args) {
24 LexicalOrderDFS obj = new LexicalOrderDFS();
25 int n = 13;
26 List<Integer> result = obj.lexicalOrder(n);
27 for (int num : result) {
28 System.out.print(num + " ");
29 }
30 }
31}In this Java code, we use an ArrayList to store result numbers. The helper method dfs is employed to explore lexicographic numbers recursively within limits.
This iterative approach attempts to simulate the depth-first search behavior using an iterative procedure. It begins by using a number and incrementally moving to the next lexicographical number by clever digit manipulations. If a number reaches an immediate boundary, it backs off accordingly to stay within valid digits.
Time Complexity: O(n), Space Complexity: O(1) (ignoring return array).
1
This C code leverages a simple iterative method to achieve lexical order. By multiplying the current index by 10, or adjusting on digit boundaries, this code manages to efficiently iterate through lexical numbers.