Simple Java DFS Solution (beats 85%, 12 lines)


  • 2
    C
    
    public class Solution {
        public List<Integer> lexicalOrder(int n) {
            List<Integer> res = new ArrayList<>(n);
            //  from  1 to 9.
            //  0 is can't be a soution.
            dfs(1, 9, n, res);
            return res;
        }
        private void dfs(int start, int end, int n, List<Integer> res){
            // <= n make the solution can't bigger than n
            for (int i = start; i <= end && i <= n; i++){
                res.add(i);
                // 10 -> next recursion: 100(->next recursion 1000), 101,102....
                // next loop: 11 -> next recursion: 110,  111,112....
                // next loop: 12 -> next recursion: 120,  121,122....
                // from 0 to 9 different from the dfs call in method lexicalOrder
                dfs(i * 10, i * 10 + 9, n, res);
            }
        }
    }
    

  • 0
    E

    @Chung this solution is great. I don't know why it does not have upvotes. Can you provide a little explanation. I'm getting a little lost in the recursion. In the case of n = 13, when our for loop eventually fails because i is no longer less than n, start = 100 and end = 109. How in the world does start and end become 10 and 19 all over again???


  • 2
    C

    @ElayMarco Here are some explanation. Hope this could help you

    public class Solution {
        public List<Integer> lexicalOrder(int n) {
            List<Integer> res = new ArrayList<>(n);
            //  from  1 to 9.
            //  0 is can't be a soution.
            dfs(1, 9, n, res);
            return res;
        }
        private void dfs(int start, int end, int n, List<Integer> res){
            // <= n make the solution can't bigger than n
            for (int i = start; i <= end && i <= n; i++){
                res.add(i);
                // 10 -> next recursion: 100(->next recursion 1000), 101,102....
                // next loop: 11 -> next recursion: 110,  111,112....
                // next loop: 12 -> next recursion: 120,  121,122....
                // from 0 to 9 different from the dfs call in method lexicalOrder
                dfs(i * 10, i * 10 + 9, n, res);
            }
        }
    }
    

Log in to reply
 

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