forked from neetcode-gh/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 1
/
332-Reconstruct-Itinerary.cs
38 lines (35 loc) · 1.15 KB
/
332-Reconstruct-Itinerary.cs
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
public class Solution {
public IList<string> FindItinerary(IList<IList<string>> tickets)
{
var map = new Dictionary<string, List<string>>();
foreach (var ticket in tickets)
{
if (!map.TryGetValue(ticket[0], out var adj))
{
adj = new List<string>();
map.Add(ticket[0], adj);
}
adj.Add(ticket[1]);
}
foreach (var adj in map.Values)
{
adj.Sort(Comparer<string>.Create((a, b) => string.Compare(b, a)));
}
var res = new Stack<string>();
DfsVisit(map, "JFK", res);
return res.ToList();
}
private void DfsVisit(Dictionary<string, List<string>> map, string src, Stack<string> ans)
{
if (map.TryGetValue(src, out var adj))
{
while (adj.Count > 0)
{
var next = adj.Last();
adj.RemoveAt(adj.Count - 1);
DfsVisit(map, next, ans);
}
}
ans.Push(src);
}
}