[leetcode]386. Lexicographical Numbers

Problem

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.

Solution

  use pre-order tree travel algorithm.

Code

class Solution {
public:
    void dfs(int x,int n,vector &ans) {
        if (x != 0) {
            ans.push_back(x);
        }
        for (int i = 0;i <= 9;i ++) {
            if (x * 10 + i > 0 && x * 10 + i <= n) {
                dfs(x * 10 + i,n,ans);
            }
        }
    }
    vector lexicalOrder(int n) {
        vector ans;
        dfs(0,n,ans);
        return ans;
    }
};