A simple JS solution properly fast.


  • 1
    A
    /**
     * @param {string[][]} tickets
     * @return {string[]}
     */
    var findItinerary = function(tickets) {
        var map = {};
        tickets = tickets.sort((a,b)=>{
            if(a[0] === b[0]) return a[1] < b[1] ? 1 : -1; 
            else return a[0] < b[0] ? 1 : -1;
        });
        for(var i = 0; i < tickets.length; i++){
            var ticket = tickets[i];
            var from = ticket[0], to = ticket[1];
            
            map[from] = map[from] || [];
            map[from].push(to);
        }
        
        function generate(from, map){
            var node = map[from], list = [from];
            while(node && node.length){
                var next = node.pop();
                list.push(next);
                node = map[next];
            }
            var len = list.length, ret = [];
            for(var i = len - 1; i >= 0; i--){
                var key = list[i];
                if(map[key] && map[key].length){
                    //detect circle
                    list[i] = generate(key, map);
                }
            }
            for(var j = 0; j < len; j++){
                var key = list[j];
                if(Array.isArray(key)){
                    ret.push.apply(ret, key);
                }else{
                    ret.push(key);
                }
            }
            return ret;
        }
    
        return generate("JFK", map);
    };

Log in to reply
 

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