Algorithm
Problem Name: 386. Lexicographical Numbers
Given an integer n, return all the numbers in the range [1, n] sorted in lexicographical order.
You must write an algorithm that runs in O(n) time and uses O(1) extra space.
Example 1:
Input: n = 13 Output: [1,10,11,12,13,2,3,4,5,6,7,8,9]
Example 2:
Input: n = 2 Output: [1,2]
Constraints:
1 <= n <= 5 * 104
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public List lexicalOrder(int n) {
List result = new ArrayList<>();
for (int i = 1; i < 10; i++) {
dfs(i, n, result);
}
return result;
}
private void dfs(int curr, int n, List < Integer> result) {
if (curr > n) {
return;
}
result.add(curr);
for (int i = 0; i < 10; i++) {
dfs(10 * curr + i, n, result);
}
}
}
Input
n = 13
Output
[1,10,11,12,13,2,3,4,5,6,7,8,9]
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const lexicalOrder = function(n) {
const result = []
for (let i = 1; i < 10; i++) {
dfs(i)
}
function dfs(n) {
if (n <= num) result.push(n)
if (10 * n <= num) {
for (let j = 0; j < 10; j++) {
dfs(10 * n + j)
}
}
}
return result
}
Input
n = 13
Output
[1,10,11,12,13,2,3,4,5,6,7,8,9]
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def lexicalOrder(self, n): return sorted(range(1, n + 1), key = str)
Input
n = 2
Output
[1,2]