2
$\begingroup$

We are given an array of $n$ Strings with total Length $K$, and we are asked to find an alphabetical order (if one exists) with respect to which the array become lexicographically sorted. The time complexity should be $O(K)$.

I think we should use some data structure like a trie, but I can't find a way to solve the problem.

$\endgroup$
3
$\begingroup$

For any pair of adjacent strings, you can find a constraint of the form $\sigma < \tau$ on the order of the symbols which is necessary in order for this pair of strings to be lexicographically ordered. This doesn't require any fancy data structure.

Putting all of these constraints together in a directed graph, you can determine whether such an order exists, and if so, find it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.