C# || Reconstruct Itinerary – How To Reconstruct Itinerary In Order Using C#

January 01, 2024 admin No comments

The following is a module with functions which demonstrates how to reconstruct itinerary in order using C#.

1. Find Itinerary – Problem Statement

You are given a list of airline tickets where tickets[i] = [from_i, to_i] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.

All of the tickets belong to a man who departs from “JFK”, thus, the itinerary must begin with “JFK”. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.

For example, the itinerary [“JFK”, “LGA”] has a smaller lexical order than [“JFK”, “LGB”].

You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.

Example 1:

Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]] Output: ["JFK","MUC","LHR","SFO","SJC"]

Example 2:

Input: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]] Output: ["JFK","ATL","JFK","SFO","ATL","SFO"] Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"] but it is larger in lexical order.

2. Find Itinerary – Solution

The following is a solution which demonstrates how to reconstruct itinerary in order.





		
		
			2. Find Itinerary - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jan 1, 2024
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to reconstruct itinerary in order
// ============================================================================
public class Solution {
    public IList<string> FindItinerary(IList<IList<string>> tickets) {
        var map = new Dictionary<string, List<string>>();

        for (int index = 0; index < tickets.Count; ++index) {
            List<string> ticket = tickets[index].ToList();
            string from = ticket[0];
            string to = ticket[1];
            if (!map.ContainsKey(from)) {
                map[from] = new List<string>();
            }
            map[from].Add(to);
        }

        foreach (List<string> list in map.Values) {
            list.Sort();
        }

        var result = new List<string>();
        string start = "JFK";
        result.Add(start);
        DFS(map, start, result, tickets.Count);
        return result;
    }

    private bool DFS(Dictionary<string, List<string>> map, string cur, List<string> result, int totalTicket) {
        if (result.Count == totalTicket + 1) {
            return true;
        }

        if (!map.ContainsKey(cur)) {
            return false;
        }

        List<string> nextList = map[cur];

        for (int index = 0; index < nextList.Count; ++index) {
            string next = nextList[index];
            if (next == null) {
                continue;
            }

            nextList[index] = null;
            result.Add(next);
            if (DFS(map, next, result, totalTicket)) {
                return true;
            }
            // back track
            result.RemoveAt(result.Count - 1);
            nextList[index] = next;
        }

        return false;
    }
}// http://programmingnotes.org/
			
				
					
				
					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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jan 1, 2024
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to reconstruct itinerary in order
// ============================================================================
public class Solution {
    public IList<string> FindItinerary(IList<IList<string>> tickets) {
        var map = new Dictionary<string, List<string>>();
 
        for (int index = 0; index < tickets.Count; ++index) {
            List<string> ticket = tickets[index].ToList();
            string from = ticket[0];
            string to = ticket[1];
            if (!map.ContainsKey(from)) {
                map[from] = new List<string>();
            }
            map[from].Add(to);
        }
 
        foreach (List<string> list in map.Values) {
            list.Sort();
        }
 
        var result = new List<string>();
        string start = "JFK";
        result.Add(start);
        DFS(map, start, result, tickets.Count);
        return result;
    }
 
    private bool DFS(Dictionary<string, List<string>> map, string cur, List<string> result, int totalTicket) {
        if (result.Count == totalTicket + 1) {
            return true;
        }
 
        if (!map.ContainsKey(cur)) {
            return false;
        }
 
        List<string> nextList = map[cur];
 
        for (int index = 0; index < nextList.Count; ++index) {
            string next = nextList[index];
            if (next == null) {
                continue;
            }
 
            nextList[index] = null;
            result.Add(next);
            if (DFS(map, next, result, totalTicket)) {
                return true;
            }
            // back track
            result.RemoveAt(result.Count - 1);
            nextList[index] = next;
        }
 
        return false;
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

["JFK","MUC","LHR","SFO","SJC"] ["JFK","ATL","JFK","SFO","ATL","SFO"]

Was this article helpful?

👍 YesNo

Posted in: C#, Console Tags: c-sharp, depth first search, dfs, leetcode

C# || Reconstruct Itinerary – How To Reconstruct Itinerary In Order Using C#

Related

Leave a ReplyCancel reply

Search

Compile Your Code Now

Translate Page

Popular Pages

Recent

Archives

Categories