AC Javascript solution with Vertex, inEdges, and BFS Topological Sort


  • 0
    S
    1. Create Vertex class with id and 2 sets: inEdges & outEdges.

    2. Build graph to store all vertices, and
      |-> setup inEdges neighbors, and
      |-> setup outEdges neighbors.

    3. Run a BFS topological sort with inEdges.size === 0 order, return "" if the result.length !== graph size.

    class Vertex {
        constructor(c) {
            this.id = c;
            this.inEdges = new Set();
            this.outEdges = new Set();
        }
        addInEdge(c) {
            this.inEdges.add(c);
        }
        
        addOutEdge(c) {
            this.outEdges.add(c);
        }
    }
    
    function alienOrder (words) {
        if (words === null || words.length === 0) return "";
        
        let graph = {};
        let result = "";
        
        for(let i = 0; i < words.length; i++){
            let word = words[i];
            // build graph
    	for(let j = 0; j < words[i].length; j++){
                if (graph[word[j]] === undefined) graph[word[j]] = new Vertex(word[j]);
            }
            // setup in and out edges
            if (i > 0) setNeighbors(words[i-1], words[i], graph);
        }
        // console.log(graph);
        return topologicalSort(graph, result);
    }
    
    function setNeighbors(s, t, graph) {
        for(let i = 0; i < Math.min(s.length, t.length); i++){
    		v1 = graph[s[i]];
    		v2 = graph[t[i]];
                    // setup in & out edges
    		if(v1.id !== v2.id){
    			v1.addOutEdge(v2.id);
    			v2.addInEdge(v1.id);
    			break;
    		}
    	}
    }
    
    function topologicalSort(graph, result) {
        let queue = [];
        for (let key in graph) {
            if (graph[key].inEdges.size === 0) queue.push(graph[key]);
        }
        while(queue.length !== 0) {
            let curr = queue.shift();
            result += curr.id;
            for(let outEdge of curr.outEdges) {
                graph[outEdge].inEdges.delete(curr.id);
                if (graph[outEdge].inEdges.size === 0) queue.push(graph[outEdge]);
            }
        }
        if(result.length !== Object.keys(graph).length) return "";
        return result;
    }
    
    

Log in to reply
 

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