Lexicographical Numbers

By | September 1, 2016
0 Comment
Share the joy
  •  
  •  
  •  
  •  
  •  
  •  

leetcode 386.

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.

Subscribe to see which companies asked this question

Solution. A great solution is from here. The result sequence is a pre-order sequence on this number tree.

lexiconumber

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

private static void dfs(int curr, int n, List<Integer> ans) {
    if (curr > n) {
        return;
    }
    ans.add(curr);
    for (int i = 0; i <= 9; i++) {
        dfs(curr * 10 + i, n, ans);
    }
}

Check my code on github.