Java Concise DFS


  • 1
    public class Solution {
        private List<String> res = new ArrayList<>();
        private int totalTickets;
        private Map<String, List<String>> graph = new HashMap<>();
        public List<String> findItinerary(String[][] tickets) {
            if (tickets == null || tickets.length == 0) return res;  
            totalTickets = tickets.length;
            for (String[] ticket : tickets) {
                if (!graph.containsKey(ticket[0])) {
                    graph.put(ticket[0], new ArrayList<>());
                }
                graph.get(ticket[0]).add(ticket[1]);
            }
            // sort in lexical order
            for (Map.Entry<String, List<String>> entry : graph.entrySet()) {
                Collections.sort(entry.getValue());
            } 
            res.add("JFK");
            dfs("JFK");
            return res;
        }
        private void dfs(String curr) {
            if (!graph.containsKey(curr)) return;
            List<String> list = graph.get(curr);
            for (int i = 0; i < list.size(); i++) {
                String dest = list.get(i);
                list.remove(i);
                res.add(dest);
                dfs(dest);
                if (res.size() == totalTickets + 1) return;
    
                list.add(i, dest);
                res.remove(res.size() - 1);
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.