# Java solution using topological sorting.

• ``````        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)
} 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;