0269-alien-dictionary.js

/**
 * BFS
 * https://leetcode.com/problems/alien-dictionary/
 * @param {string[]} words
 * @return {string}
 */
 var alienOrder = function(words) {
    const { graph, frequencyMap, queue, buffer } = buildGraph(words);

    if (!canBuildGraph(words, graph, frequencyMap)) return '';

    queueSources(queue, frequencyMap);
    bfs(queue, frequencyMap, graph, buffer);

    return (frequencyMap.size <= buffer.length)
        ? buffer.join('')
        : '';
}

var initGraph = () => ({
    graph: new Map(),
    frequencyMap: new Map(),
    queue: new Queue(),
    buffer: [],
})

var buildGraph = (words) => {
    const { graph, frequencyMap, queue, buffer } = initGraph();

    for (const word of words) {
        for (const char of word) {
            frequencyMap.set(char, 0);
            graph.set(char, []);
        }
    }

    return { graph, frequencyMap, queue, buffer };
};

var canBuildGraph = (words, graph, frequencyMap) => {
    for (let index = 0; (index < words.length - 1); index++) {
        const [ word1, word2 ] = [ words[index], words[(index + 1)] ];
        const minLength = Math.min(word1.length, word2.length)

        const isWord1Longer = (word2.length < word1.length);
        const isPrefix = isWord1Longer && word1.startsWith(word2);

        if (isPrefix) return false;

        for (let j = 0; (j < minLength); j++) {
            const [ char1, char2 ] = [ word1[j], word2[j] ];

            const isEqual = (char1 === char2);
            if (isEqual) continue;

            graph.get(char1).push(char2);
            frequencyMap.set(char2, frequencyMap.get(char2) + 1);

            break;
        }
    }

    return true;
};

const bfs = (queue, frequencyMap, graph, buffer) => {
    while (!queue.isEmpty()) {
        for (let level = (queue.size() - 1); (0 <= level); level--) {
            checkNeighbors(queue, frequencyMap, graph, buffer)
        }
    }
};

var checkNeighbors = (queue, frequencyMap, graph, buffer) => {
    const char = queue.dequeue();

    buffer.push(char);

    for (const next of graph.get(char)) {
        const value = (frequencyMap.get(next) - 1);

        frequencyMap.set(next, value);

        const isEmpty = (frequencyMap.get(next) === 0);
        if (!isEmpty) continue;

        queue.enqueue(next);
    }
}

const queueSources = (queue, frequencyMap) => {
    for (const [ key, value ] of frequencyMap) {
        const isEmpty = (frequencyMap.get(key) === 0);
        if (!isEmpty) continue;

        queue.enqueue(key);
    }
}

/**
 * DFS
 * https://leetcode.com/problems/alien-dictionary/
 * @param {string[]} words
 * @return {string}
 */
 var alienOrder = function(words) {
    const { graph, seen, buffer } = buildGraph(words);

    if (!canBuildGraph(words, graph)) return '';

    for (const [ char ] of graph) {
        if (!dfs(char, graph, seen, buffer)) return '';
    }

    return buffer.reverse().join('')
}

var initGraph = () => ({
    graph: new Map(),
    seen: new Map(),
    buffer: [],
})

var buildGraph = (words) => {
    const { graph, seen, buffer } = initGraph();

    for (const word of words) {
        for (const char of word) {
            graph.set(char, []);
        }
    }

    return { graph, seen, buffer };
};

var canBuildGraph = (words, graph) => {
    for (let index = 0; (index < words.length - 1); index++) {
        const [ word1, word2 ] = [ words[index], words[(index + 1)] ];
        const minLength = Math.min(word1.length, word2.length)

        const isWord1Longer = (word2.length < word1.length);
        const isPrefix = isWord1Longer && word1.startsWith(word2);

        if (isPrefix) return false;

        for (let j = 0; (j < minLength); j++) {
            const [ char1, char2 ] = [ word1[j], word2[j] ];

            const isEqual = (char1 === char2);
            if (isEqual) continue;

            graph.get(char1).push(char2);
    
            break;
        }
    }

    return true;
};

const dfs = (char, graph, seen, buffer) => {
    if (seen.has(char)) return seen.get(char);

    if (!backTrack(char, graph, seen, buffer)) return false;

    buffer.push(char);

    return true;
}

const backTrack = (char, graph, seen, buffer) => {
    seen.set(char, false);
        for (const neighbor of graph.get(char)) {
            if (!dfs(neighbor, graph, seen, buffer)) return false;
        }
    seen.set(char, true);

    return true;
}