Comment on page

# 386.Lexicographical-Numbers

## 题目描述

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.

## 代码

### Approach #1 DFS

Time: O(1) && Space: O(1)
public class Solution {
public List<Integer> lexicalOrder(int n) {
List<Integer> res = new ArrayList<>(n);
// from 1 to 9.
// 0 is can't be a soution.
dfs(1, 9, n, res);
return res;
}
private void dfs(int start, int end, int n, List<Integer> res){
// <= n make the solution can't bigger than n
for (int i = start; i <= end && i <= n; i++){
// 10 -> next recursion: 100(->next recursion 1000), 101,102....
// next loop: 11 -> next recursion: 110, 111,112....
// next loop: 12 -> next recursion: 120, 121,122....
// from 0 to 9 different from the dfs call in method lexicalOrder
dfs(i * 10, i * 10 + 9, n, res);
}
}
}
public class Solution {
public List<Integer> lexicalOrder(int n) {
List<Integer> res = new ArrayList<>();
for(int i=1;i<10;++i){
dfs(i, n, res);
}
return res;
}
public void dfs(int cur, int n, List<Integer> res){
if(cur>n)
return;
else{
for(int i=0;i<10;++i){
if(10*cur+i>n)
return;
dfs(10*cur+i, n, res);
}
}
}
}

### Approach #2 Iteration

public class Solution {
public List<Integer> lexicalOrder(int n) {
List<Integer> ans = new ArrayList<>(n);