Leetcode #332. Reconstruct Itinerary

[yokostan]

DFS + adjList:

class Solution {

    public HashMap<String, ArrayList<String>> adjList = new HashMap<>();
    public List<String> res = new ArrayList<String>();
    public int numTickets = 0;
    public int numTicketsUsed = 0;

    public List<String> findItinerary(List<List<String>> tickets) {
        numTickets = tickets.size();
        if (tickets == null || tickets.size() == 0) return res;
        for (List<String> ticket : tickets) {
            if (!adjList.containsKey(ticket.get(0))) {
                adjList.put(ticket.get(0), new ArrayList<String>());
            }
            adjList.get(ticket.get(0)).add(ticket.get(1));
        }

        for (Map.Entry<String, ArrayList<String>> entry : adjList.entrySet()) {
            Collections.sort(entry.getValue());
        }

        res.add("JFK");
        dfs("JFK");
        return res;
    }

    public void dfs(String v) {
        if (!adjList.containsKey(v)) return ;
        List<String> list = adjList.get(v);
        for (int i = 0; i < list.size(); i++) {
            String neighbor = list.get(i);
            list.remove(i);
            res.add(neighbor);
            numTicketsUsed++;
            dfs(neighbor);
            if (numTickets == numTicketsUsed) return ;
            list.add(i, neighbor);
            res.remove(res.size() - 1);
            numTicketsUsed--;
        }
    }
}

DFS with PriorityQueue:

class Solution {

    public HashMap<String, PriorityQueue<String>> adjList = new HashMap<>();
    public List<String> res = new ArrayList<String>();

    public List<String> findItinerary(List<List<String>> tickets) {
        if (tickets == null || tickets.size() == 0) return res;
        for (List<String> ticket : tickets) {
            if (!adjList.containsKey(ticket.get(0))) {
                adjList.put(ticket.get(0), new PriorityQueue<String>());
            }
            adjList.get(ticket.get(0)).add(ticket.get(1));
        }

        dfs("JFK");
        Collections.reverse(res);
        return res;
    }

    public void dfs(String v) {
        while (adjList.containsKey(v) && !adjList.get(v).isEmpty()) {
            dfs(adjList.get(v).poll());
        }
        res.add(v);
    }
}