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:
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.

Solution

public class Solution {
    public List<String> findItinerary(String[][] tickets) {
        List<String> ans = new ArrayList<String>();
        if(tickets == null || tickets.length == 0) return ans;

        Map<Integer, List<Integer> > map = new HashMap<Integer, List<Integer>>();
        for(int i = 0; i < tickets.length; i++) {
            int from = hash(tickets[i][0]);
            int to   = hash(tickets[i][1]);
            if(!map.containsKey(from)) map.put(from, new ArrayList<Integer>());
            map.get(from).add(to);
        }

        for(Integer start: map.keySet()) Collections.sort(map.get(start));

        Stack<Integer> path = new Stack<Integer>();
        path.add(hash("JFK"));
        while(path.size() != 0) {
            int cur = path.peek();
            List<Integer> dst = map.get(cur);
            if( dst == null || dst.size() == 0) {
                ans.add(decode(path.pop()));    
            } else {
                path.push(dst.remove(0));
            }        
        }

        List<String> realAns = new ArrayList<String>();
        for(int i = 0; i < ans.size(); i++) realAns.add(ans.get(ans.size() - i - 1));
        return realAns;
    }


    public int hash(String city) {
        return ( (int)city.charAt(0) << 16) | ( (int)city.charAt(1) << 8) | ( (int)city.charAt(2));
    }

    public String decode(int c) {
        return ""+
        (char) ((c >> 16)&0xFF) + 
        (char) ((c >> 8)&0xFF) + 
        (char) ((c)&0xFF);
    }
}