Find Itinerary from a given list of tickets - GeeksforGeeks
Read full article from Find Itinerary from a given list of tickets - GeeksforGeeks
Given a list of tickets, find itinerary in order using the given list.
Example:
Input: "Chennai" -> "Banglore" "Bombay" -> "Delhi" "Goa" -> "Chennai" "Delhi" -> "Goa" Output: Bombay->Delhi, Delhi->Goa, Goa->Chennai, Chennai->Banglore,
It may be assumed that the input list of tickets is not cyclic and there is one ticket from every city except final destination.
One Solution is to build a graph and do Topological Sorting of the graph. Time complexity of this solution is O(n).
We can also use hashing to avoid building a graph. The idea is to first find the starting point. A starting point would never be on ‘to’ side of a ticket. Once we find the starting point, we can simply traverse the given map to print itinerary in order. Following are steps
1) Create a HashMap of given pair of tickets: dataset
2) Find the starting point of itinerary. a) Create a reverse HashMap.
b) Traverse 'dataset'. For every key of dataset, check if it is there in 'reverseMap'. If a key is not present, then we found the starting point. In the above example, "Bombay" is starting point. 3) Start from above found starting point and traverse the 'dataset' to print itinerary.
private
static
void
printResult(Map<String, String> dataSet)
{
// To store reverse of given map
Map<String, String> reverseMap =
new
HashMap<String, String>();
// To fill reverse map, iterate through the given map
for
(Map.Entry<String,String> entry: dataSet.entrySet())
reverseMap.put(entry.getValue(), entry.getKey());
// Find the starting point of itinerary
String start =
null
;
for
(Map.Entry<String,String> entry: dataSet.entrySet())
{
if
(!reverseMap.containsKey(entry.getKey()))
{
start = entry.getKey();
break
;
}
}
// If we could not find a starting point, then something wrong
// with input
if
(start ==
null
)
{
System.out.println(
"Invalid Input"
);
return
;
}
// Once we have starting point, we simple need to go next, next
// of next using given hash map
String to = dataSet.get(start);
while
(to !=
null
)
{
System.out.print(start +
"->"
+ to +
", "
);
start = to;
to = dataSet.get(to);
}
}