Iterative way to construct the list, very straightforward and easy to understand.


  • 0
    R

    the basic idea is relatively easy. We can construct the list by searching each element one by one in lexicographical order. Imagine how you are searching a word in a dictionary: first find the first character of the word and then the second and then third, etc. This problem is very similar, except that you need to find all the words from 1-n.
    We can use a prefix to simulate the word searching process, and add each number which is in the range of 1-n. See the code for details. I think it's very easy to understand though.

      public List<Integer> lexicalOrder(int n) {
            List<Integer> result = new ArrayList<Integer>();
            helper(n, 0, result);
            return result;
        }
        
        private void helper(int n, int prefix, List<Integer> result) {
            for (int i = 0; i <= 9; i++) {
                int val = prefix*10 + i;
                if (val > n) {
                    return;
                }
                if (val != 0) {
                    result.add(val);
                    helper(n, val, result);
                }
            }
        }
    
    

Log in to reply
 

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