# 386.Lexicographical-Numbers

## ้ข็ฎๅฐๅ

https://leetcode.com/problems/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);
for (int i = 1, prev = 1; i < n; ++i) {
if (prev * 10 <= n) {
prev *= 10;
} else {
while (prev % 10 == 9 || prev == n) prev /= 10;
prev++;
}