Lexicographical Numbers : Beauty of DFS

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.

See the beauty of DFS

Solution

import java.util.*;
public class Main {
    public static void main(String args[]) {
        // Your Code Here
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		scan.close();
		
		List<Integer> list = new ArrayList<>();
		for(int i=1;i<10;i++)
		{
			dfs(i,n,list);
		}
		for(Integer num : list)
			System.out.print(num + " ");
    }
	public static void dfs(int cur,int n,List<Integer> list)
	{
		if(cur > n)
			return;
		list.add(cur);
		for(int i=0;i<10;i++)
		{
			if(10*cur+i > n)
				return;
			dfs(10*cur+i,n,list);
		}
	}
}

Leave a Comment

Your email address will not be published. Required fields are marked *