StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Use a directed graph with 26 vertices, each vertex represents a character. An edge from vertex A to vertex B means in the alphabet B is in front of A. </p> <p>The first step is to establish such a graph with only vertices but NO edges.</p> <p>Second, you scan the input dictionary, word by word. And compare each word with the previous word. You should find exact one relationship for each word you scanned. So you add an edge in this graph. Assume the dictionary is correct, there should be no conflicts.</p> <p>After you finished the dictionary, you output the alphabet by </p> <ol> <li>pick a random vertex, traverse its path until you find the one character that points to nothing. This is the first character in the alphabet. Output it and delete it from the graph.</li> <li>keep doing 1 until all vertices are deleted.</li> </ol> <p>EDIT: To better explain this algorithm, let's run it on your sample input.</p> <p>Input: {"zebra', "apple", "cat", "crass"}</p> <p>Word 0 and word 1, we immediately know that z comes before a, so we make an edge a->z</p> <p>Word 1 and word 2, we immediately know that a comes before c, so we make another edge c->a</p> <p>Word 2 and Word 3, the first letters are the same "c", but the second ones differ, so we learn that a comes before r, so we have another edge r->a</p> <p>Now all the words are read. Output the order by pick up a vertex randomly (say we pick c), then we have c->a->z in the graph. Output z and delete z from the graph (mark it as NULL). Now pick another one (say we pick r), then we find r->a in the graph. We output a and delete a from graph. Now we pick another one (say we pick c again), there's no path found, so we just output c and delete it. Now we pick the last one, r, there's no path again, so we output r and delete it. Since all vertices are deleted, the algorithm is done.</p> <p>The output is z, a, c, r. The ordering of "c" and "r" are random since we don't really know their relationship from the input.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload