Very Short Iterative Java Solution

  • 13

    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>());
        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.