Tuesday, June 7, 2016

Leetcode: 332. Reconstruct Itinerary

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.
  1. 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"].
  2. All airports are represented by three capital letters (IATA code).
  3. You may assume all tickets form at least one valid itinerary.
Example 1:
tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Return ["JFK", "MUC", "LHR", "SFO", "SJC"].
Example 2:
tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Return ["JFK","ATL","JFK","SFO","ATL","SFO"].
Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.
Special thanks to @dietpepsi for adding this problem and creating all test cases.
Understand the problem:
Classical graph problem. Use DFS + backtracking. 

Code (Java):
public class Solution {
    public List<String> findItinerary(String[][] tickets) {
        List<String> result = new ArrayList<>();
        if (tickets == null || tickets.length == 0) {
            return result;
        // step 1: build the ajdList
        Map<String, List<String>> adjList = new HashMap<>();
        for (String[] ticket : tickets) {
            String from = ticket[0];
            String to = ticket[1];
            if (adjList.containsKey(from)) {
            } else {
                List<String> neighbors = new ArrayList<>();
                adjList.put(from, neighbors);
        // step 2: sort the adjlist according to lex order
        for (String from : adjList.keySet()) {
            List<String> neighbors = adjList.get(from);
        // step 3: start the dfs
        findItineraryHelper("JFK", adjList, result);
        return result;
    private void findItineraryHelper(String curr, Map<String, List<String>> adjList, List<String> result) {
        List<String> neighbors = adjList.get(curr);
        if (neighbors != null) {
            while (neighbors.size() > 0) {
                String neighbor = neighbors.get(0);
                findItineraryHelper(neighbor, adjList, result);
        result.add(0, curr);


  1. Which is better Pepsi or Coke?
    SUBMIT YOUR ANSWER and you could receive a prepaid VISA gift card!

  2. New Diet Taps into Pioneering Plan to Help Dieters Get Rid Of 12-23 Pounds within Only 21 Days!