Given set of words that are lexicographically sorted, return lexicographic order.
E.g:
abc acd bcc bed bdc dabThe order of letters for the given example would be
a->b->c->e->dTime:
Part-1:
Complexity of constructing graph: \$O(n * m)\$, where \$n\$ is number of words and \$m\$ is max length of any word.
Part-2:
Topological sort: \$O(V + E)\$, where \$V\$ is number of vertices and \$E\$ is number of edges
Space:
\$O(V + E)\$ - entire graph is stored
Looking for request code review, optimizations and best practices. Also verifying if how would final answer for complexity look like.
E.g: Would it be \$O(n*m + E + V)\$?
class GraphLexico<T> implements Iterable<T> {
/* A map from nodes in the graph to sets of outgoing edges. Each
* set of edges is represented by a map from edges to doubles.
*/
private final Map<T, List<T>> graph = new HashMap<T, List<T>>();
/**
* Adds a new node to the graph. If the node already exists then its a
* no-op.
*
* @param node Adds to a graph. If node is null then this is a no-op.
* @return true if node is added, false otherwise.
*/
public boolean addNode(T node) {
if (node == null) {
throw new NullPointerException("The input node cannot be null.");
}
if (graph.containsKey(node)) return false;
graph.put(node, new ArrayList<T>());
return true;
}
/**
* Given the source and destination node it would add an arc from source
* to destination node. If an arc already exists then the value would be
* updated the new value.
*
* @param source the source node.
* @param destination the destination node.
* @param length if length if
* @throws NullPointerException if source or destination is null.
* @throws NoSuchElementException if either source of destination does not exists.
*/
public void addEdge (T source, T destination) {
if (source == null || destination == null) {
throw new NullPointerException("Source and Destination, both should be non-null.");
}
if (!graph.containsKey(source) || !graph.containsKey(destination)) {
throw new NoSuchElementException("Source and Destination, both should be part of graph");
}
/* A node would always be added so no point returning true or false */
graph.get(source).add(destination);
}
/**
* Given a node, returns the edges going outward that node,
* as an immutable map.
*
* @param node The node whose edges should be queried.
* @return An immutable view of the edges leaving that node.
* @throws NullPointerException If input node is null.
* @throws NoSuchElementException If node is not in graph.
*/
public List<T> edgesFrom(T node) {
if (node == null) {
throw new NullPointerException("The node should not be null.");
}
List<T> edges = graph.get(node);
if (edges == null) {
throw new NoSuchElementException("Source node does not exist.");
}
return Collections.unmodifiableList(graph.get(node));
}
/**
* Returns the iterator that travels the nodes of a graph.
*
* @return an iterator that travels the nodes of a graph.
*/
@Override public Iterator<T> iterator() {
return graph.keySet().iterator();
}
}
public final class LexicographicalSort {
private LexicographicalSort() {}
/**
* Returns the list of characters in lexicographically sorted order.
*
* Note that if entire information needed to determine lexicographical
* order is not present then results are unreliable.
*
* @param dictionary the list of words ordered in lexicographical order
*/
public static List<Character> lexigoGraphicOrder(List<String> dictionary) {
final GraphLexico<Character> graph = new GraphLexico<Character>();
for (int i = 0; i < dictionary.size() - 1; i++) {
createGraph(dictionary.get(i), dictionary.get(i + 1), graph);
}
return topologicalSort(graph);
}
/**
* Creates a DAG based on the lexicographical order.
*
*
* @param string1 the first string with higher placement/priority in dictionary
* @param string2 the second string with lesser placement/priority in dictionary
* @param graph the DAG to be constructed.
*/
private static void createGraph(String string1, String string2, GraphLexico<Character> graph) {
char[] ch1 = string1.toCharArray();
char[] ch2 = string2.toCharArray();
// pick the smaller length
int minLength = ch1.length > ch2.length ? ch2.length : ch1.length;
for (int i = 0; i < minLength; i++) {
if (ch1[i] != ch2[i]) {
graph.addNode(ch1[i]);
graph.addNode(ch2[i]);
graph.addEdge(ch1[i], ch2[i]);
return;
}
}
}
/**
* Running the topological sort, on the constructed graph
*
*
* @param graph the DAG determining priority of characters
* @return the characters in lexicographic order
*/
private static List<Character> topologicalSort(GraphLexico<Character> graph) {
final GraphLexico<Character> reverseGraph = reverseGraph(graph);
final List<Character> result = new ArrayList<Character>();
final Set<Character> visited = new HashSet<Character>();
final Set<Character> finished = new HashSet<Character>();
for (Character node : reverseGraph) {
explore(node, result, visited, finished, reverseGraph);
}
return result;
}
private static void explore (Character node, List<Character> result, Set<Character> visited,
Set<Character> finished, GraphLexico<Character> reverseGraph) {
if (visited.contains(node)) {
if (finished.contains(node)) return;
else throw new IllegalArgumentException("Cycle detected. ");
}
visited.add(node);
for(Character currNode : reverseGraph.edgesFrom(node)) {
explore(currNode, result, visited, finished, reverseGraph);
}
finished.add(node);
result.add(node);
}
private static GraphLexico<Character> reverseGraph(GraphLexico<Character> graph) {
final GraphLexico<Character> graphRev = new GraphLexico<Character>();
for (Character node : graph) {
graphRev.addNode(node);
}
for (Character node : graph) {
for (Character neighbors : graph.edgesFrom(node)) {
graphRev.addEdge(neighbors, node);
}
}
return graphRev;
}
}
Followed by testing
public class LexicographicalSortTest {
@Test
public void testLexicoGraphicalSort() {
List<String> list = new ArrayList<String>();
list.add("abc");
list.add("acd");
list.add("bcc");
list.add("bed");
list.add("bdc");
list.add("dab");
List<Character> expectedList = new ArrayList<Character>();
expectedList.add('a');
expectedList.add('b');
expectedList.add('c');
expectedList.add('e');
expectedList.add('d');
assertEquals(expectedList, LexicographicalSort.lexigoGraphicOrder(list));
}
}
