Very Short Iterative Java Solution


  • 12
    8

    Just using a hashmap and stack to replace recursion.

    public List<String> findItinerary(String[][] tickets) {
        LinkedList<String> ret = new LinkedList<String>();
        Map<String, PriorityQueue<String>> map = new HashMap<String, PriorityQueue<String>>();
        Stack<String> stack = new Stack<String>();
        for(String[] t : tickets) {
            if(!map.containsKey(t[0])) map.put(t[0], new PriorityQueue<String>());
            map.get(t[0]).offer(t[1]);
        }
        stack.push("JFK");
        while(!stack.isEmpty()) {
            String next = stack.peek();
            if(map.containsKey(next) && map.get(next).size() > 0) stack.push(map.get(next).poll());
            else ret.addFirst(stack.pop());
        }
        return ret;
    }

Log in to reply
 

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