Javascript solution, 160ms, inspired by Java Greedy Solution


  • 0
    C

    Inspired by Java Greedy Solution , here is the javascript code. Here is the thought:

    1. Sort the tickets with alphabetical, then generate a "hash map" to store all tickets with key-value.

    2. After got the alphabetical hash map, get the results with greedy strategy. This is like the DFS.

    3. Once got one best way and there are still tickets left, need to go back (say point x) and find another way. Since there always a way to have all tickets, so at point x, there wil be one or more circles.

    `

    var findItinerary = function(tickets) {
        if (tickets == null || tickets.length == 0) return [];
        var map = {};
        var result = [];
        
        tickets.sort(sortArray);
        for(var i = 0; i < tickets.length; i++) {
            if(tickets[i][0] in map) map[tickets[i][0]].push(tickets[i][1]);
            else map[tickets[i][0]] = [tickets[i][1]];
        }
        
        var key = 'JFK';
        var drawback = [];
        for(var i = 0; i < tickets.length; i++) {
            while(!(key in map) || map[key].length == 0) {
                drawback.push(key);
                key = result.pop();
            }
            result.push(key);
            key = map[key].shift();
        }
        result.push(key);
        while(drawback.length > 0) result.push(drawback.pop());
    
        return result;
        
                        
    };
    
    function sortArray(a,b) {
        if(a[0] == b[0]) return (a[1] < b[1] ? -1: (a[1] > b[1] ? 1: 0));
    
        return (a[0] < b[0] ? -1 : 1);
    }
    

Log in to reply
 

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