Given set of words that are lexicographically sorted, return lexicographic order Eg:

abc

acd

bcc

bed

bdc

dab

The order of letters for the given example would be a->b->c->e->d

Time:

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: Topololical 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.

Eg: 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));
    }

}