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 Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s