Monday, June 6, 2016

Reconstruct Itinerary

I didn't think of using DFS approach at first and use a map instead. So I stuck when it reaches the end of the itinerary but the map is yet empty. Then I searched online for a while and realize it is a DFS problem, all I need to add with my first approach is to use a Stack. Later I use recursion again, and the first one is actually neater.

Iteration:

public List<string> findItinerary(String[][] tickets) {
        List<string> rst = new ArrayList<>();
        if (tickets == null || tickets.length == 0)
            return rst;
        Map<string, priorityqueue<string>> map = new HashMap<>();
        for (String[] ticket : tickets) {
            String from = ticket[0];
            if (!map.containsKey(from)) {
                map.put(from, new PriorityQueue<>());
            }
            map.get(from).add(ticket[1]);
        }
        Stack<string> temp = new Stack();
        temp.add("JFK");
        while (!temp.isEmpty()) {
            String from = temp.peek();
            if (map.containsKey(from) && map.get(from).size() > 0)
                temp.push(map.get(from).poll());
            else
                rst.add(temp.pop());
            }
        Collections.reverse(rst);
        return rst;
    }


Recursion:
public List findItinerary(String[][] tickets) {
        List<string> itinerary = new ArrayList<>();
        if (tickets == null || tickets.length == 0)
            return itinerary;
        Map<string, priorityqueue<string>> destinations = new HashMap<>();
        for (String[] ticket : tickets) {
            if (!destinations.containsKey(ticket[0]))
                destinations.put(ticket[0], new PriorityQueue<>());
            destinations.get(ticket[0]).offer(ticket[1]);
        }
        findItinerary("JFK", destinations, itinerary);
        Collections.reverse(itinerary);
        return itinerary;
        
    }
    private void findItinerary(String from, Map<string, priorityqueue<string>> destinations, List<string> itinerary) {
        if (!destinations.containsKey(from) || destinations.get(from).size() == 0) {
            itinerary.add(from);
            return;
        }
        PriorityQueue<string> curr = destinations.get(from);
        while (!curr.isEmpty()) {
            String to = curr.poll();
            findItinerary(to, destinations, itinerary);
        }
        itinerary.add(from);
    }

No comments:

Post a Comment