将字母以最快的顺序按字典顺序重新排列

问题描述 投票:1回答:1

考虑一下我们的名单,其中没有两个人是同一个人的名字。列表的最大大小为:

现在的目标是找出如果我们改变了英文字母的顺序,那么在词典编排顺序中首先出现的名字是多少(以及哪个!)!例如,如果列表为:

ha haa st

然后更改字母,我们可以将ha

st放在首位,但是无论我们如何对其进行更改haa总是在ha之后,因此可以使用两个名称首先。

当然,有一种蛮力的方法来找出答案,但这需要检查所有26个答案!每个单词可能的字母顺序!由于此问题的时限为1秒

,所以我认为找到O(nlogn)或更低的算法是可行的。但是我不知道如何解决这个问题。我使用trie会有所帮助(因为我在学习数据结构时遇到了这个问题!),但是图形算法也可能会有所帮助。

如何找到正确的算法和解决此问题的方法,以及如何在代码中实现它?

考虑一下我们的名单,其中没有两个人是同一个人的名字。列表的最大大小为:现在的目标是找出可以出现的名字(和名字!)先出现的数量...

algorithm data-structures trie alphabetical-sort
1个回答
1
投票

w成为第一个单词

© www.soinside.com 2019 - 2024. All rights reserved.