Simple Java DFS Solution


  • 106
    X
    The idea is pretty simple. If we look at the order we can find out we just keep adding digit from 0 to 9 to every digit and make it a tree.
    Then we visit every node in pre-order. 
           1        2        3    ...
          /\        /\       /\
       10 ...19  20...29  30...39   ....
    
    
    public class Solution {
        public List<Integer> lexicalOrder(int n) {
            List<Integer> res = new ArrayList<>();
            for(int i=1;i<10;++i){
              dfs(i, n, res); 
            }
            return res;
        }
        
        public void dfs(int cur, int n, List<Integer> res){
            if(cur>n)
                return;
            else{
                res.add(cur);
                for(int i=0;i<10;++i){
                    if(10*cur+i>n)
                        return;
                    dfs(10*cur+i, n, res);
                }
            }
        }
    }
    
    

  • 0
    G

    Thank you so much. The diagrams help a lot, way better and easier to digest it than the code.


  • 3
    D

    This is a very good solution, though I think it is pretty slow. Around 1000ms if written in C++.


  • 0
    R

    This method makes it solvable in the time limit given in the interview. That's why I find it better than other methods. Thank you!


  • 4
    L
    if(10*cur+i>n) return;
    

    This statement is very important, which can improve the performance by twice!


  • 0
    C

    Awesome and thank you so much


  • 0
    D

    Nice solution. Could you explain why you have to check for if(10*cur+i>n) within the loop if you check at the beginning of the function?


  • 0
    N

    @dr.pro my c++ is about 479 ms, if you break inside the loop


  • 0
    R

    Thank you for such a great explanation.


  • 0
    Q

    I came with the same idea :)

    public class Solution {
        public List<Integer> lexicalOrder(int n) {
            List<Integer> list = new LinkedList<>();
            for (int i = 1; i < 10; ++ i)
                generate(i, n, list);
            return list;
        }
        
        private void generate(int num, int n, List<Integer> list) {
            if (num > n) return;
            list.add(num);
            num *= 10;
            for (int i = 0; i < 10; ++ i) {
                if (num > n) break;
                generate(num ++, n, list);
            }
        }
    }
    

  • 1
    Q

    What a brilliant solution easily understandable! Here is some icing on the cake:
    The dfs function already checked the condition (10*cur+i>n), before calling itself on this checked parameter. I think we can optimize by just checking one time.

    Here is a solution inspired by your algorithms (185ms):

    public List<Integer> lexicalOrder(int n) {
        // DFS based solution:
        List<Integer> res = new ArrayList<>();
        
        for(int i = 1; i < 10 & i <= n; i++) {
            dfs(i, n, res);
        }
        return res;
    }
    
    private void dfs(int m, int n, List<Integer> res) {
        res.add(m);
        for (int i = m * 10; i <= n && i < m * 10 + 10; i++) {
            dfs(i, n, res);
        }
    }

  • 0
    S

    Simple and clear to a hard problem!


  • 0
    C
    This post is deleted!

  • 0
    H

    The question said the input could be 5,000,000, anyone tested this number using this solution ?


  • 1
    O

    Here's mine:

        public List<Integer> lexicalOrder(int n) {
            List<Integer> l = new LinkedList();
            addNums(0, n, l);
            l.remove(0);
            return l;
        }
        
        private void addNums(int offset, int n, List<Integer> l) {
            for (int i = offset; i < offset + 10 && i <= n; i++) {
                l.add(i);
                if (i > 0 && i * 10 <= n)
                    addNums(i * 10, n, l);
            }
        }
    

  • 0
    W

    C++ version

    class Solution {
    public:
        vector<int> lexicalOrder(int n) {
            vector<int> result;
            dfs(result, 0, n);
            result.erase(result.begin());
            return result;
        }
        
    private:
        void dfs(vector<int>& result, int num, const int n) {
            for(int i = num; i <= min(n, num+9); i++) {
                result.push_back(i);
                if(i != 0 && 10*i <= n) dfs(result, 10*i, n);
            }
        }
    };
    

  • 0
    C

    Thanks for sharing. Here is mine https://discuss.leetcode.com/topic/73994/simple-java-dfs-solution-beats-85-12-lines

    public class Solution {
        public List<Integer> lexicalOrder(int n) {
            List<Integer> res = new ArrayList<>(n);
            dfs(1, 9, n, res);
            return res;
        }
        private void dfs(int start, int end, int n, List<Integer> res){
            for (int i = start; i <= end && i <= n; i++){
                res.add(i);
                dfs(i * 10, i * 10 + 9, n, res);
            }
        }
    }
    

  • 1
    A

    @xialanxuan1015 What will be the complexity of this solution?


  • 0

    @lxyscls Do you know why it improves performance so much?


  • 0
    M

    @说出来你可能不信 Early termination. This line can decrease recursion depth.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.