Java 11ms solution(HashMap & sorted List)


  • 22
    G
    public class Solution {
        public List<String> findItinerary(String[][] tickets) {
            ArrayList<String> result = new ArrayList<String>();
            
            if(tickets == null || tickets.length == 0){
                return result;
            }
            
            int total = tickets.length + 1;
            
            HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
            
            for(int i = 0; i < tickets.length; i++){
                if(map.containsKey(tickets[i][0])){
                    ArrayList<String> tmp = map.get(tickets[i][0]);
                    listAdd(tickets[i][1], tmp);
                }
                else{
                    ArrayList<String> tmp = new ArrayList<String>();
                    tmp.add(tickets[i][1]);
                    map.put(tickets[i][0], tmp);
                }
            }
            
            result.add("JFK");
            
            itineraryHelper("JFK", map, result, total, 1);
            
            return result;
        }
        
        public boolean itineraryHelper(String current, HashMap<String, ArrayList<String>> map, ArrayList<String> result, int total, int num){
            
            if(num >= total){
                return true;
            }
            
            if(!map.containsKey(current) || map.get(current).size() == 0){
                return false;
            }
            
            ArrayList<String> curList = map.get(current);
            int i = 0;
            
            while(i < curList.size()){
                String next = curList.remove(i);
                result.add(next);
                
                if(itineraryHelper(next, map, result, total, num + 1)){
                    return true;
                }
                
                result.remove(result.size() - 1);
                listAdd(next, curList);
                i++;
            }
            
            return false;
        }
        
        
        public void listAdd(String value, ArrayList<String> list){
            if(list.size() == 0){
                list.add(value);
                return;
            }
            else{
                int i = 0;
                while(i < list.size()){
                    if(value.compareTo(list.get(i)) <= 0){
                        list.add(i, value);
                        return;
                    }
                    i++;
                }
                list.add(value);
                return;
            }
        }
        
    }

  • 0
    N

    I liked your solution. It is very straightforward dfs. The code is very easy to understand without explanation.


  • 0
    I

    Upvoted it. Nice and clean.

    What's the time complexity of this DFS?


  • 0
    G

    really awesome


  • 0

    Very straightforward solution, but you may need a PriorityQueue<String> to clean up the following ugly code:

    public void listAdd(String value, ArrayList<String> list){
            if(list.size() == 0){
                list.add(value);
                return;
            }
            else{
                int i = 0;
                while(i < list.size()){
                    if(value.compareTo(list.get(i)) <= 0){
                        list.add(i, value);
                        return;
                    }
                    i++;
                }
                list.add(value);
                return;
            }
        }
    

  • 2
    N

    @CodingFlower

    I don't think priorityQueue will work in this case. This is simply backtracking.

    If you use the priorityQueue, since you need to try every element in that heap, and doing dfs. When you poll out the head element, try to search it and it does not work, backtracking told that you should put it back but where to put it, still put to the head? Since you need the next head element in the next recursion. So you can't put it back.

    That's why he use a SortedList. The advantage of list to the priorityQueue is that in sorted list, you know the index for each element.


  • 0
    S

    I tried implementing PriorityQueue based solution using same approach. But it gives TLE for some tests.

    public class Solution {
        private static class City implements Comparable{
            String city;
            int rank;
            City(String city, int rank) {
                this.city = city;
                this.rank = rank;
            }
            
            public int compareTo( Object o ) {
                City other = (City) o;
                if (this == other ) return 0;
                if ( this.rank == other.rank ) return this.city.compareTo(other.city);
                return Integer.compare(this.rank, other.rank);
            }
        }
        
        public List<String> findItinerary(String[][] tickets) {
            if( tickets == null ) {
                return Collections.EMPTY_LIST;
            }   
            
            Map<String, PriorityQueue<City>> ticketMap = new HashMap<String, PriorityQueue<City>>();
            for ( String[] ticket : tickets ) {
                if ( !ticketMap.containsKey(ticket[0])) {
                    ticketMap.put(ticket[0], new PriorityQueue<City>());
                }
                
                ticketMap.get(ticket[0]).offer(new City(ticket[1], 1));
            }
            
            List<String> result = new ArrayList<String>();
            String origin = "JFK";
            result.add(origin);
            
            _findItinerary(ticketMap, origin, result, 1, tickets.length+1);
            
            return result;
        }
        
        private boolean _findItinerary(Map<String, PriorityQueue<City>> map, String origin, List<String> result, int index, int count ) {
            if ( index == count ) {
                return true;
            }
            
            if ( !map.containsKey(origin) || map.get(origin).isEmpty()) {
                return false;
            }
            
            int size = map.get(origin).size();
            while( size-- >= 0 ) {
                City destination = map.get(origin).poll();
                result.add( destination.city );
                if ( _findItinerary(map, destination.city, result, index+1, count)) {
                    return true;
                }
                result.remove(result.size()-1);
                destination.rank++;
                map.get(origin).offer( destination );
            }
            return false;
        }
    }
    

  • 0
    C
    This post is deleted!

  • 0
    S
    This post is deleted!

Log in to reply
 

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