332.Reconstruct-Itinerary

332. Reconstruct Itinerary

题目地址

https://leetcode.com/problems/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.

Note:
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"].
All airports are represented by three capital letters (IATA code).
You may assume all tickets form at least one valid itinerary.

Example 1:
Input: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Output: ["JFK", "MUC", "LHR", "SFO", "SJC"]

Example 2:
Input: [["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.

代码

Approach #1 Backtracking + Greedy

class Solution {
  HashMap<String, List<String>> flightMap = new HashMap<>();
  HashMap<String, boolean[]> visitBitmap = new HashMap<>();
  int flights = 0;
  List<String> result = null;

  public List<String> findItinerary(List<List<String>> tickets) {
        for (List<String> ticket: tickets) {
      String origin = ticket.get(0);
      String dest = ticket.get(1);
      if (this.flightMap.containsKey(origin)) {
        List<String> destList = flightMap.get(origin);
        destList.add(dest);
      } else {
        List<String> destList = new LinkedList<String>();
        destList.add(dest);
        flightMap.put(origin, destList);
      }
    }

    for (Map.Entry<String, List<String>> entry: flightMap.entrySet()) {
      Collections.sort(entry.getValue());
      visitBitmap.put(entry.getKey(), new boolean[entry.getValue().size()]);
    }

    flights = tickets.size();
    LinkedList<String> route = new LinkedList<String>();

    backtracking("JFK", route);
    return result;
  }

  private boolean backtracking(String origin, LinkedList<String> route) {
    if (route.size() == flights + 1) {
      result = (List<String>) route.clone();
        return true;
    }

    if (!this.flightMap.containsKey(origin))        return false;

    int i = 0;
    boolean[] bitmap = visitBitmap.get(origin);

    for (String dest: flightMap.get(origin)) {
      if (!bitmap[i]) {
        bitmap[i] = true;
        route.add(dest);
        boolean ret = backtracking(dest, route);
        route.pollLast();
        bitmap[i] = false;

        if (ret)     return true;
      }
      i++;
    }

    return false;
  }
}