My Concise JAVA solution based on Topological Sorting


  • 12

    This problem is actually similar as Course Schedule II. The basic idea to solve this problem:

    1. Convert characters to a graph: Adjacency lists
    2. Topological sorting: keep adding elements whose in-degree is 0
    

    While figuring out the solution, it helped me to understand topological sorting entirely.

    Topological sorting: The classic linear algorithm to solve dependency problems, e.g. course schedule.

    In-degree: The amount of dependencies of the element E, which means the amount of E's predecessors. We have to fulfill E's predecessors before executing E, when E's in-degree = 0.

    Time complexity = O(n + m) - n represents all vertices, m represents all edges

    JAVA Code:

    public String alienOrder(String[] words) {
        List<Point> pairs = new LinkedList<Point>(); // Adjacency list: pair = (node, node's predecessor)
        Set<Character>chs = new HashSet<Character>();// All distinct characters
    
        // 1. Convert characters to a graph: Adjacency lists 
        for (int i = 0; i < words.length; i++) {            
            String word = words[i];     
            boolean alreadySet = false;// Only set one pair where the characters at the same position differs in two neighbor rows. e.g. "wrtk" < "wrfp"=> 't' < 'f'
            for (int j = 0; j < words[i].length(); j++) {                
                if (!alreadySet && i > 0 && j < words[i-1].length() && words[i].charAt(j) != words[i-1].charAt(j)) {// Set dependency of two characters by comparing two neighbor rows. 
                    pairs.add(new Point(words[i].charAt(j), words[i-1].charAt(j)));
                    alreadySet = true;
                }               
                chs.add(word.charAt(j));// Add distinct character to chs set
            }
        }       
    
        // 2. Topological sorting: keep adding elements whose in-degree is 0
        String res = "";
        int indegree[] = new int[256];
        Arrays.fill(indegree, Integer.MIN_VALUE);
    
        for (Character ch : chs) indegree[ch] = 0;// Initialize in-degree of the distinct characters in the words list
        for (int i = 0; i < pairs.size(); i++)// Increase in-degree according to the dependency of pairs list
            indegree[pairs.get(i).x]++;
    
        Queue<Character> queue = new LinkedList<Character>();
        for (int i = 0; i < 256; i++) {
            if (indegree[i] == 0) {// Add the character whose in-degree = 0, which means it doesn't have any predecessor 
                res += (char) i;
                queue.offer((char) i);
            }
        }
    
        while (!queue.isEmpty()) {
            Character predecessor = queue.poll(); // Dequeue the character whose in-degree = 0 from queue
    
            for (int i = 0; i < pairs.size(); i++) {
                if (pairs.get(i).y == predecessor) {// Update in-degree: decrease 1 to the successors of the character whose in-degree = 0
                    indegree[pairs.get(i).x]--;                 
                    if (indegree[pairs.get(i).x] == 0) {// If in-degree = 0, add the character to the queue, and append it to the result string
                        res += (char) pairs.get(i).x; 
                        queue.offer((char) pairs.get(i).x);
                    }
                }
            }
        }
        return res.length() == chs.size() ? res : "";// NOTE: res.length should equal the size of distinct characters, otherwise a cycle must exist 
    }
    

  • 0
    Y
        Great solution, and it pass the test cases.
         But only one place I don't quite understand,
         when you build the graph:
         if (words[i].charAt(j) != words[i-1].charAt(j)) {
         pairs.add(new Point(words[i].charAt(j), words[i-1].charAt(j)));
         I think this statement is wrong, for example in English:
          ba>ac in lexicographically  but you cannot say that 
         a>c(word[0].charAt(1),word[1].charAt(1) in lexicographically.
    

  • 0
    S
    This post is deleted!

  • 1

    Thanks for your comment, yidong! In the case ba>ac, only b>a will be set, then the locker 'alreadySet'=true, which prevents the cases after b.


  • 1

    Updated the corresponding part, hope it's clearer now ;)


  • 0
    A
    This post is deleted!

  • 0

    Runs in 5ms

    public class Solution {
        public String alienOrder(String[] words) {
            if(words==null || words.length==0) return "";
            boolean[][] graph=new boolean[26][26];
            //indegree array used to record the indegree of character and also whether the character exists in alien dictionary 
            int[] indegree=new int[26];
            /*indegree[i] = -1 means the character doesn't exist in alien dictionary
                             0 means the character's indegree is 0
                             n means the character's indegree is n
             */
            Arrays.fill(indegree, -1);
            char[] pre=words[0].toCharArray(), current=null;
            /*compare two consecutive words in the alien dictionary, find the first two different character and draw a line from the pre-word's character to current-word's character
            (suppose we are drawing a graph from character a to character b if a comes before b)
            */
            for(char x:pre) indegree[x-'a']=0;
            for(int i=1;i<words.length;i++){
                current=words[i].toCharArray();
                for(char x: current) indegree[x-'a']=0;
                int index=0;
                while(index<pre.length&&index<current.length&&pre[index]==current[index]) index++;
                /* handle the cases that one of the word is the prefix of another word
                For example: "wrt" follows by "wrtff" or
                             "wrtff" follows by "wrt"
                the first case should be correct, the second one is assumed incorrect
                */
                if(index==current.length){
                    if(pre.length==current.length) continue;
                    else return "";
                }
                if(index==pre.length) continue;
                graph[pre[index]-'a'][current[index]-'a']=true;
                pre=current;
            }
            /* alphabetCount record how many characters that exist in alien dictionary, We are gonna use this variable to check whether the graph we build has cycle inside
            */
            int alphabetCount=0;
            for(int a: indegree){
                if(a==0) alphabetCount++;
            }
            //caculate each character's indegree
            for(int i=0;i<26;i++){
                for(int j=0;j<26;j++){
                    if(graph[i][j]){
                        indegree[j]++;
                    }
                }
            }
            LinkedList<Integer> queue=new LinkedList<>();
            for(int i=0;i<26;i++){
                if(indegree[i]==0) queue.offer(i);
            }
            StringBuilder order=new StringBuilder();
            while(!queue.isEmpty()){
                int tmp=queue.poll();
                order.append((char)('a'+tmp));
                for(int next=0;next<26;next++){
                    if(graph[tmp][next]){
                        if(--indegree[next]==0) queue.offer(next);
                        graph[tmp][next]=false;
                    }
                }
            }
            return order.length()==alphabetCount?order.toString():"";
        }
    }
    

Log in to reply
 

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