leetcodesolutions/code/332.reconstruct-itinerary.java at main · Raghuram42/leetcodesolutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
// class Solution {
//     List<String> re ;
//     HashMap<String, ArrayList<String>> res;
//     HashSet<String> vis;
//     public List<String> findItinerary(List<List<String>> tickets) {
//         res = new HashMap<String, ArrayList<String>>();

//         for(List<String> place: tickets){
//             if(!res.containsKey(place.get(0)))
//             res.put(place.get(0), new ArrayList<String>());

//             res.get(place.get(0)).add(place.get(1));
//         }
//         Collections.sort(res.get("JFK"));
//         System.out.println(res);
//         re =  new ArrayList<String>();
//         vis = new HashSet<String>();
//         dfs("JFK");
//         //re.add("JFK");
//         return re;
//     }

//     public void dfs(String i){
//         //re.add(i);
//        // System.out.println(i);
//         if(!res.containsKey(i) || vis.contains(i)){
//          //re.add(i);
//             return;
//         }
//         for(String str: res.get(i)){
//             vis.add(i);
//             dfs(str);
//             re.add(str);
//         }


//     }
// }


public class Solution{
	HashMap<String, PriorityQueue<String>> map = new HashMap<String, PriorityQueue<String>>();
	LinkedList<String> result = new LinkedList<String>();

	public List<String> findItinerary(List<List<String>> tickets) {
		for (List<String> ticket : tickets) {
			if (!map.containsKey(ticket.get(0))) {
				PriorityQueue<String> q = new PriorityQueue<String>();
				map.put(ticket.get(0), q);
			}
			map.get(ticket.get(0)).offer(ticket.get(1));
		}

		dfs("JFK");
		return result;
	}

	public void dfs(String s) {
		PriorityQueue<String> q = map.get(s);

		while (q != null && !q.isEmpty()) {
			dfs(q.poll());
		}

		result.addFirst(s);
	}
}