Algorithm
Problem Name: 332. Reconstruct Itinerary
You are given a list of airline tickets where tickets[i] = [fromi, toi] 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.
Constraints:
1 <= tickets.length <= 300tickets[i].length == 2fromi.length == 3toi.length == 3fromiandtoiconsist of uppercase English letters.fromi != toi
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int cmp(const void *a, const void *b) {
const char **s1 = *(const char ***)a, **s2 = *(const char ***)b;
int c = strcmp(s1[0], s2[0]);
if (c) return c;
return strcmp(s1[1], s2[1]);
}
int dfs(int *v, char ***tickets, int n, char **p, int last, int d) {
int i;
if (d == n) {
p[n] = tickets[last][1];
return 1;
}
for (i = 0; i < n; i ++) {
if (!v[i] && !strcmp(tickets[last][1], tickets[i][0])) {
v[i] = 1;
p[d] = tickets[i][0];
if (dfs(v, tickets, n, p, i, d + 1)) return 1;
v[i] = 0;
}
}
return 0;
}
char** findItinerary(char*** tickets, int ticketsRowSize, int ticketsColSize, int* returnSize) {
int *v, i, done;
char **p;
qsort(tickets, ticketsRowSize, sizeof(char **), cmp);
p = malloc((ticketsRowSize + 1) * sizeof(char *));
v = calloc(ticketsRowSize, sizeof(int));
//assert(p && v);
done = 0;
for (i = 0; !done && i < ticketsRowSize; i ++) {
if (!strcmp(tickets[i][0], "JFK")) {
v[i] = 1;
p[0] = tickets[i][0];
done = dfs(v, tickets, ticketsRowSize, p, i, 1);
v[i] = 0;
}
}
*returnSize = ticketsRowSize + 1;
free(v);
return p;
}
Input
tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output
["JFK","MUC","LHR","SFO","SJC"]
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<string> findItinerary(vector<pair, greaterm;
vector < string>res;
for(auto x: tickets) m[x.first].push(x.second);
DFS("JFK", res, m);
reverse(res.begin(), res.end());
return res;
}
void DFS(string cur, vector < string>& res, unordered_map, greater& m){
while(!m[cur].empty()){
string s = m[cur].top();
m[cur].pop();
DFS(s, res, m);
}
res.push_back(cur);
}
};
Input
tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output
["JFK","MUC","LHR","SFO","SJC"]
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public List findItinerary(List();
for (List ticket : tickets) {
String from = ticket.get(0);
String to = ticket.get(1);
map.computeIfAbsent(from, k -> new PriorityQueue < >()).add(to);
}
Stack stack = new Stack<>();
LinkedList < String> result = new LinkedList<>();
stack.push("JFK");
while (!stack.isEmpty()) {
String destination = stack.peek();
if (!map.getOrDefault(destination, new PriorityQueue < >()).isEmpty()) {
stack.push(map.get(destination).remove());
} else {
result.addFirst(stack.pop());
}
}
return result;
}
}
Input
tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output
["JFK","ATL","JFK","SFO","ATL","SFO"]
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def findItinerary(self, tickets):
graph, stack, reached = collections.defaultdict(list), ["JFK"], []
for a, b in tickets: heapq.heappush(graph[a], b)
while stack:
if graph[stack[-1]]: stack.append(heapq.heappop(graph[stack[-1]]))
else: reached.append(stack.pop())
return reached[::-1]
Input
tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output
["JFK","ATL","JFK","SFO","ATL","SFO"]
#5 Code Example with C# Programming
Code -
C# Programming
using System;
using System.Collections.Generic;
namespace LeetCode
{
public class _0332_ReconstructItinerary
{
public IList < string> FindItinerary(IList();
foreach (var ticket in tickets)
{
if (!map.ContainsKey(ticket[0]))
map.Add(ticket[0], new MinPriorityQueue());
map[ticket[0]].Insert(ticket[1]);
}
var result = new List < string>();
Visit("JFK", map, result);
return result;
}
private void Visit(string airport, IDictionary < string, MinPriorityQueue> map, IList route)
{
while (map.ContainsKey(airport) && map[airport].Size() > 0)
{
var target = map[airport].DeleteMin();
Visit(target, map, route);
}
route.Insert(0, airport);
}
public class MinPriorityQueue : PriorityQueue
{
public MinPriorityQueue() : base() { }
public MinPriorityQueue(int initCapacity) : base(initCapacity) { }
protected override void Sink(int k)
{
while (2 * k < = N)
{
int j = 2 * k;
if (j < N && pq[j].CompareTo(pq[j + 1]) > 0) j++;
if (pq[k].CompareTo(pq[j]) < = 0) break;
Swap(k, j);
k = j;
}
}
protected override void Swim(int k)
{
while (k > 1 && pq[k / 2].CompareTo(pq[k]) > 0)
{
Swap(k / 2, k);
k = k / 2;
}
}
public string Min() => First();
public string DeleteMin() => Delete();
}
public abstract class PriorityQueue
{
protected int N;
protected string[] pq;
public PriorityQueue() : this(1) { }
public PriorityQueue(int initCapacity)
{
this.N = 0;
pq = new string[initCapacity + 1];
}
public bool IsEmpty() => N == 0;
public int Size() => N;
public string First()
{
if (IsEmpty()) { throw new ArgumentOutOfRangeException(); }
return pq[1];
}
public void Insert(string x)
{
if (N >= pq.Length - 1)
Resize(pq.Length * 2);
pq[++N] = x;
Swim(N);
}
protected abstract void Swim(int k);
public string Delete()
{
var result = pq[1];
Swap(1, N--);
Sink(1);
pq[N + 1] = string.Empty;
if (N > 0 && N == (pq.Length - 1) / 4)
Resize(pq.Length / 2);
return result;
}
protected abstract void Sink(int k);
private void Resize(int newCapacity)
{
var temp = new string[newCapacity + 1];
for (int i = 1; i < = N; i++)
temp[i] = pq[i];
pq = temp;
}
protected void Swap(int index1, int index2)
{
var temp = pq[index1];
pq[index1] = pq[index2];
pq[index2] = temp;
}
}
}
}
Input
tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output
["JFK","MUC","LHR","SFO","SJC"]