标题似乎是一个很常见的问题,但请耐心等待。

基本上,让我们在字符串的每个索引处说出您知道该索引中可能包含哪些字母,然后您要查找按字典顺序排列的最小排列。

因此,例如:

Index  |  Options
-------|----------
  1    |  'b'
  2    |  'c', 'a'
  3    |  'd', 'c'
  4    |  'c', 'a'

因此,o / p应该是badc。是的,顺便说一句,字符不能重复,所以没有贪婪算法。

我认为我们可以通过创建队列或某种字符串来使用某种广度优先搜索,并且每次我们发现无法创建另一个排列时,都可以将其从列表中弹出。尽管怀疑这是最佳的,但必须在O(N)中。有任何想法吗?

不,我不认为C不好,但是我更喜欢C / C++中的代码片段:p

谢谢!

最佳答案

这可以通过匹配算法解决。您可以使用网络流解决方案来解决此问题。这可以分解为二部图问题。

确切地说,最大权重分配问题或最大成本最大匹配将是一个解决方案。

以下是两部分顶点集-

LEVEL          Alphabets
 1                 a
 2                 b
 3                 c
 4                 d
                   e
                   .
                   .
                   .
                   z

现在,仅当且仅当那些是该级别的选项时,才将其从设置级别分配到设置字母。因此,这里将是这些边缘-{1,b},{2,a},{2,c},{3,c},{3,d},{4,a},{4,c}
现在,要获得字典上最少的结果,您需要以这种方式为边缘分配权重-
Edge Wt. = 26^(N-Level) * ('z' - Alphabet)

因此,例如,边缘{2,c}的边缘权重为
26^(4-2) * (26-3) =  26^2*23

现在,您可以使用标准的最大成本最大匹配解决方案。这是一个多项式解。就我现在所想,这将是最好的方法。天真的解决方案是26 ^ N的指数解决方案,因此我认为您会对多项式解决方案感到满意。

关于c++ - 查找某个字符串的按字典顺序排列的最小排列,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/39635178/

10-13 06:52
查看更多