Given an integer n
, return all the numbers from 1 to n
in lexicographical order.
To generate numbers in lexicographical order, we can use a depth-first search (DFS) approach. By iteratively exploring numbers starting from each digit (1 through 9), we ensure that numbers are processed in a lexicographical sequence.
n
.O(n), where n
is the input number. Each number from 1 to n
is processed once.
O(n), for storing the result list and the recursion stack.
class Solution {
public:
vector<int> lexicalOrder(int n) {
vector<int> result;
function<void(int)> dfs = [&](int baseIndex) {
if (baseIndex * 10 > n) {
return;
}
for (int i = baseIndex * 10; i < baseIndex * 10 + 10 && i <= n; ++i) {
result.push_back(i);
dfs(i);
}
};
for (int i = 1; i <= 9 && i <= n; ++i) {
result.push_back(i);
dfs(i);
}
return result;
}
};
class Solution:
def lexicalOrder(self, n: int) -> List[int]:
result = []
def dfs(baseIndex):
if baseIndex * 10 > n:
return
for i in range(baseIndex * 10, baseIndex * 10 + 10):
if i > n:
break
result.append(i)
dfs(i)
for i in range(1, 10):
if i > n:
break
result.append(i)
dfs(i)
return result
class Solution {
public List<Integer> lexicalOrder(int n) {
List<Integer> result = new ArrayList<>();
dfs(result, n);
return result;
}
private void dfs(List<Integer> result, int n) {
for (int i = 1; i <= 9 && i <= n; i++) {
result.add(i);
dfsHelper(result, i, n);
}
}
private void dfsHelper(List<Integer> result, int baseIndex, int n) {
if (baseIndex * 10 > n) {
return;
}
for (int i = baseIndex * 10; i < baseIndex * 10 + 10 && i <= n; i++) {
result.add(i);
dfsHelper(result, i, n);
}
}
}
var lexicalOrder = function (n) {
const arr = [];
function dfs(baseIndex) {
if (baseIndex * 10 > n) {
return;
}
for (let i = baseIndex * 10; i < baseIndex * 10 + 10 && i <= n; i++) {
arr.push(i);
dfs(i);
}
}
let stack = [];
for (let i = 1; i <= 9 && i <= n; i++) {
arr.push(i);
dfs(i);
}
return arr;
};