Java solution using DFS, very clean and easy to understand


  • 0
    H

    Step 1: Construct the graph;
    Step 2: Apply DFS to each node. When we visit a node for the first time, node.start = ++timestamp; when we finished the DFS on current node, node.finish = ++timestamp;
    Step 3: Sort the nodes by node.finish in descending order. This is a typical way to implement topological sort.

    Note: If the order is invalid, then there must be at least one cycle in the graph. We can use DFS to detect cycles. When we visit a node during DFS, if its start time is not zero but its finish time is zero, then there must be a cycle here.

    public class Solution {
        private int timestamp;
        
        public String alienOrder(String[] words) {
            Node[] nodes = new Node[26];
            
            for (int i = 0; i < words.length; i++) {
                for (int j = 0; j < words[i].length(); j++) {
                    char ch = words[i].charAt(j);
                    if (nodes[ch - 'a'] == null) nodes[ch - 'a'] = new Node(ch);
                }
                if (i == 0) continue;
                for (int j = 0; j < words[i - 1].length() && j < words[i].length(); j++) {
                    char ch1 = words[i - 1].charAt(j);
                    char ch2 = words[i].charAt(j);
                    if (ch1 != ch2) {
                        nodes[ch1 - 'a'].set.add(nodes[ch2 - 'a']);
                        break;
                    }
                }
            }
            
            for (Node node: nodes) {
                if (node != null && !DFS(node)) return "";
            }
            
            PriorityQueue<Node> queue = new PriorityQueue<Node>();
            for (Node node: nodes) {
                if (node != null) queue.offer(node);
            }
            
            String result = "";
            while (!queue.isEmpty()) {
                result += queue.poll().ch;
            }
            
            return result;
        }
        
        private boolean DFS(Node node) {
            if (node.start > 0) return node.finish > 0;
            
            node.start = ++timestamp;
            for (Node n: node.set) {
                if (!DFS(n)) return false;
            }
            node.finish = ++timestamp;
            
            return true;
        }
        
        
        class Node implements Comparable<Node> {
            Set<Node> set = new HashSet<Node>();
            int start;
            int finish;
            char ch;
            
            public Node(char ch) {
                this.ch = ch;
            }
            
            @Override
            public int compareTo(Node that) {
                return that.finish - this.finish;
            }
        }
    }
    

Log in to reply
 

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