Algorithm

LeetCode/Lexicographical Numbers

Problem Summary

Given an integer n, return all numbers in [1,n] in lexicographical order.

n ≤ 5,000,000.

Solution 1: DFS

Of course we can sort the numbers in lexicographical order, but that would take O(n × logn) time.

Starting from a 1-digit number, we can keep trying to append different digits to generate new numbers in lexicographical order. So we can use dfs. And it only takes O(n) time.

Solution 2: straight forward

If we have a number D = (d1, d2, d3, …, dm) with m digits, and the ith digit of D is di, what’s the next number? Clealy, we can get the “smallest” number by appending “0” to D. So if 10 × D ≤ n, the next number is 10 × D. Otherwise,

  1. If dm < 9 and D < n, we just increase the last digit. The next number is (d1, d2, …, dm + 1).

  2. If the last digit can’t be increased, we need to go back to increase the last digit that can be increased. Suppose it’s di, then the next number is (d1, d2, …, di + 1).

The time complexity is also O(n).

Code 1: DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> lexicalOrder(int n) {
        vector<int> res;
        for (int i = 1; i < 10; ++i)
            dfs(i, n, res);
        
        return res;
    }
    
    void dfs(int cur, int n, vector<int> &res) {
        if (cur > n)
            return;
        res.push_back(cur);
        
        int v = cur * 10;
        for (int i = 0; i < 10; ++i)
            dfs(v + i, n, res);
    }
};

Code 2: straight forward

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> lexicalOrder(int n) {
        vector<int> res(n);
        
        int cur = 1;
        for (int i = 0; i < n; ++i) {
        	res[i] = cur;
        	if (cur * 10 <= n)
        		cur *= 10;
        	else {
        		while (cur == n || cur % 10 == 9)
        			cur /= 10;
        		
        		++cur;
        	}
        }
        
        return res;
    }
};