2

字符串的数量可以很大，如 30000。给定 N 个字符串，在修改英文字母后输出哪些字符串在字典上最少。例如acdbe......

例如，如果字符串是：

omm
moo
mom
ommnom

“妈妈”在最初的英文字母中已经是字典顺序最少的了。我们可以通过在字母表中切换“m”和“o”（“abcdefghijklonmpqrstuvwxyz”）来最小化“omm”这个词。其他那些你不能按字典顺序排列的首先，不管你做什么。

有什么快速的方法吗？我没有办法解决这个问题，除非尝试每一个可能的字母表

4

1 回答 1

0

You want to be able to say weather one of the strings (say s) can be made smaller. You can turn this into a problem for detection of cycles in a graph. Here is how:

Consider the graph consisting of 26 vertices: V = { 'a', 'b', ..., 'z' } Suppose that s is the smallest and consider the letters of s in order, first then second ect.

When you are considering the first letter you know that s[0] should be smaller than x[0] for all other strings x. Now add an edge in the graph from s[0] to x[0] for all x for which they are not the same letter. The edge means "smaller than". Now consider the second letter but only look at those string that had the same first letter as s. Do the same thing - add an edge from s1 to y1 for all y in this reduces set. Then move to the third letter and consider only the strings that had the same first and second letter.. And so on (you can use a Set data structure which first contains all the strings but s and you would remove from it as you go).

Now after you have the graph built you want to know if there is a cycle or not. Indeed, if there is a cycle this means that this s cannot be the smallest, because following the cycle you will have to make the first letter in the cycle smaller than itself, which is impossible. On the other hand if you don't have a cycle, then the graph is a DAG (directed acyclic graph) and any DAG can be topologically sorted, which means its vertices (i.e. the letters of the alphabet) can be ordered in such a way so that any edge goes from smaller to larger. With this order you'll have s be the smallest because of how the graph was constructed.

You can look about detecting cycles in directed graphs - it's very common problem, whose complexity is O(|V|+|E|). In this case |V| = 26 and |E| <= n (because every time when you add an edge in the graph you reduce the set of the strings to check by one).

Thus the complexity is O(n).

If you want to check each of the strings you'll get an overall complexity of O(n^2).

于 2012-12-17T00:25:44.367 回答