Java Easy Solution beats 86% using HashMap and Recursion


  • -1
    H
    public class Solution {
        public List<String> findItinerary(String[][] tickets) {
            Map<String, List<String>> graph = new HashMap<String, List<String>>();
            for(String[] ticket:tickets){
                String from = ticket[0], to = ticket[1];
                if(!graph.containsKey(from)) graph.put(from, new ArrayList<String>());
                if(!graph.containsKey(to)) graph.put(to, new ArrayList<String>());
                addNodesHelper(graph.get(from), to);
            }
            int num = tickets.length;
            int cnt = 0;
            List<String> route = new ArrayList<String>();
            route.add("JFK");
            findItinerary(graph, route, cnt, num);
            return route;
        }
        private void addNodesHelper(List<String> nodes, String newNode){
            for(int i=0;i<nodes.size();i++){
                if(nodes.get(i).compareTo(newNode)>0){
                    nodes.add("");
                    int j=nodes.size()-1;
                    while(j>i){
                        nodes.set(j, nodes.get(j-1));
                        --j;
                    }
                    nodes.set(j, newNode);
                    return;
                }
            }
            nodes.add(newNode);
        }
        private boolean findItinerary(Map<String, List<String>> graph, List<String> route, int cnt, int num){
            if(cnt==num) return true;
            String cur = route.get(route.size()-1);
            int i=0;
            List<String> nexts = graph.get(cur);
            while(i<nexts.size()){
                String next = nexts.get(i);
                nexts.remove(i);
                route.add(next);
                if(findItinerary(graph, route, cnt+1, num)){
                    return true;
                }else{
                    route.remove(route.size()-1);
                }
                addNodesHelper(nexts, next);
                ++i;
            }
            return false;
        }
    }

Log in to reply
 

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