332-Reconstruct-Itinerary.js

/**
 * https://leetcode.com/problems/reconstruct-itinerary/
 * @param {string[][]} tickets
 * @return {string[]}
 */
var findItinerary = (tickets) => {
    tickets.sort();

    const graph = buildGraph(tickets);

    return dfs(tickets, graph);
};

const dfs = (tickets, graph, city = 'JFK', path = ['JFK']) => {
    const isBaseCase = (path.length === (tickets.length + 1));
    if (isBaseCase) return true;

    const queue = (graph.get(city) || []);

    const isEmpty = (queue.length === 0);
    if (isEmpty) return false;

    for (const nextCity of queue.slice()) {
        path.push(nextCity);
        queue.shift();

        if (dfs(tickets, graph, nextCity, path)) return path;

        path.pop();
        queue.push(nextCity);
    }

    return false;
};


const buildGraph = (tickets, graph = new Map()) => {
    for (const [ src, dst ] of tickets) {
        const edges = (graph.get(src) || []);

        edges.push(dst);
        graph.set(src, edges);
    }

    return graph;
}