Q32 Reconstruct Itinerary - leetcode 332 (eularian path && Eularian cycle)
Thu Jun 08 2023 11:05:19 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
public LinkedList<String> ans = new LinkedList<>();
public HashMap<String , PriorityQueue<String>> graph = new HashMap<>();
public List<String> findItinerary(List<List<String>> tickets) {
/* Q32 of graph playlist , eularian path and circuit ,
we have to use every ticket once or every edge once which is a eularian path .
1)make graph of HM<string , PQ<string>>
2)fire DFS
3)add nodes while backtracking in linkedlist int addfirst manner
-> LL is used as addfirst in LL is O(1)
*/
//making graph
for(List<String> nodes : tickets){
String a = nodes.get(0) , b = nodes.get(1);
graph.computeIfAbsent(a , k -> new PriorityQueue<>()).add(b);
}
//firing DFS
DFS("JFK");
return ans;
}
public void DFS(String source){
PriorityQueue<String> pq = graph.get(source);
//might be that PQ of some node is not even initiallized therefore check for null
//going to neighours
while(pq != null && pq.size() > 0){
String nbrs = pq.remove();
DFS(nbrs);
}
//adding nodes while backtracking
ans.addFirst(source);
}
}
content_copyCOPY
https://leetcode.com/problems/reconstruct-itinerary/
Comments