Java solution using topological sorting.


  • -1
    M
            public class Solution {
                
                public static class Node {
                    public char c;
                    public List<Node> lexicographicallyLowerNodes;
                    public boolean tempMark;
                    public boolean permMark;
                }
                
                
                // Create a graph with each character as a node which is connected to 
                // lexicographically lower characters.
                // Then do a topological traversal.
                
                // https://en.wikipedia.org/wiki/Topological_sorting 
                //  On above page look at - Relation to partial orders
                
                HashMap<Character, Node> allNodes = new HashMap<Character,Node>();
                ArrayList<Node> list = new ArrayList<Node>();
                public String alienOrder(String[] words) {
                    
                    String[] rows = words;
                    
                    // find max length for strings in array so that when we iterate over 
                    // each column we know the  max column.
                    
                    int maxLength = 0;
                    
                    for (String w : rows) {
                        maxLength = Math.max(maxLength, w.length());
                    }
                    
                    // go column by column. Inner loop would be row by row. 
                   // As long as row prefix is same for that column, next row column character is lower
                   //  lexicographically from previous row column character 
                    for (int column = 0; column < maxLength; column++) {
                        // current row prefix for column
                        String prefix = null;
                        // previous row column character
                        Node previous = null;
                        for (String w : rows) {
                            String myPrefix = null;
                            if (column == 0) 
                                myPrefix="";
                            else if (w.length() > column)
                                myPrefix = w.substring (0, column);
                            
                            // my row does not have column characters but less so skip
                            if (myPrefix == null)
                                continue;
                            if (prefix == null || !prefix.equals(myPrefix)) {
                                // row prefix is no longer same with this row so switch prefix.
                                prefix = myPrefix;
                                previous = null;
                            } 
                            Node n = allNodes.get(w.charAt(column));
                            if (n == null) {
                                n = new Node();
                                n.c = w.charAt(column);
                                n.lexicographicallyLowerNodes = new ArrayList<Node>();
                                allNodes.put (n.c, n);
                            }
                            if (previous != null) {
                                // don't put dependency to yourself
                                if (previous != n)
                                    previous.lexicographicallyLowerNodes.add(n);
                            } else {
                            }
                            previous = n;
                        }
                    }
                    // go through all top nodes and flatten
                    for (Node aNode : allNodes.values()) {
                        if (aNode.permMark)
                           continue;
                        boolean result = visit (aNode);
                        if (result == false) 
                            return "";
                    }
                    StringBuffer strBuffer = new StringBuffer();
                    for (Node lNode : list) {
                        strBuffer.append(lNode.c);
                    }
                    // return "result" + topNodes.size();
                    return strBuffer.toString();
                }
                
                boolean visit (Node n) {
                    if (n.tempMark) {
                        System.out.println (n.c + " has tempmark");
                        return false;
                    }
                    n.tempMark = true;
                    for (Node d : n.lexicographicallyLowerNodes) {
                        if (!d.permMark) {
                           boolean returnValue = visit (d);
                           if (!returnValue) 
                               return returnValue;
                        }
                    }
                    n.tempMark = false;
                    n.permMark = true;
                    list.add(0, n);
                    return true;
                }
            }

Log in to reply
 

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