0386. Lexicographical Numbers

https://leetcode.com/problems/lexicographical-numbers

Description

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

ac

It's more like a tricky math problem instead of practical algorithm problem.

https://leetcode.com/problems/lexicographical-numbers/discuss/86231/Simple-Java-DFS-Solution

class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> res = new ArrayList<>();
        for (int i = 1; i <=9; i++) dfs(n, i, res);
        return res;
    }

    public boolean dfs(int n, int k, List<Integer> res) {
        // exit
        if (k > n) return false;
        if (k != 0) res.add(k);

        for (int i = 0; i <= 9; i++) {
            if (!dfs(n, k * 10 + i, res)) break;
        }

        return true;
    }
}

/*
10-nodes tree, pre-order traversal, same as #440
*/