0

有人问我一个问题

Find the longest alphabetically increasing or equal string 
composed of those letters. Note that you are allowed to drop 
unused characters.

So ghaaawxyzijbbbklccc returns aaabbbccc.

Is an O(n) solution possible?

我实现了它的代码 [in python]

s = 'ghaaawxyzijbbbklccc'
lst = [[] for i in range(26)]

for ch in s:
    ml = 0
    for i in range(0,ord(ch) + 1 - ord('a')):
        if len(lst[i]) > len(lst[ml]):
            ml= i
    cpy = ''.join(lst[ml])
    lst[ord(ch) - ord('a')] = cpy + ch

ml = 0
for i in range(26):
    if len(lst[i]) > len(lst[ml]):
        ml = i
print lst[ml]

答案是'aaabbbccc'

我已经尝试了一些更多的例子并且所有的作品！并且据我所知，这段代码的复杂度是 O(N) 让我们举个例子，假设我有一个字符串 'zzzz' 所以主循环将运行 4 次，内部循环将运行 26 次迭代，所以我们可以说在最坏的情况下代码将运行

O(26*N + 26)
---------^-
this is the last iteration

所以 O(N) 可以接受吗？

现在的问题是

  1. 它是否适用于 O(N)我在 ideone 的代码
  2. 如果它在 O(N) 中工作，那么为什么要使用 DP 的 O(N2)代码的 DP
  3. 比这个代码更好吗？朋友代码
  4. 此代码的限制
4

2 回答 2

2
  1. 是 O(N)
  2. '为什么要使用 O(N2) 的 DP'：你不需要解决这个问题。但是请注意，您利用了序列标记（字母）是有限的这一事实 - 因此您可以设置一个列表来保存所有可能的起始值（26），您只需要查找该列表中最长的成员- O(1) 操作。对于具有任意数量的有序标记的序列，可以在 O(NlogN) 中完成更通用的解决方案。

  3. 你朋友的代码基本上是一样的，只是将字母映射到数字，他们的 26 个起始位置的列表包含 26 个字母计数的数字——他们不需要做任何一个。但是，从概念上讲，它是同一件事 - 保存一个列表列表。

    “更好”是一个见仁见智的问题。尽管它具有相同的渐近复杂度，但常数项可能不同，因此一个可能比另一个执行得更快。此外，在存储方面，一个可能会比另一个使用更多的内存。在如此低的情况下n，判断哪个更具可读性可能比任一算法的绝对性能更重要。我不打算做出判断。

    您可能会注意到“获胜”序列是平局的细微差别。例如-在edxeducation您拥有的测试字符串上-您的实现返回ddin，而您朋友的返回ddio。两者对我来说似乎都是有效的——没有打破这种联系的规则。

  4. 此代码的主要限制是它只能处理在一种特定情况下完全由字母组成的序列。您可以扩展它以处理大写和小写字母，或者将它们视为相同，或者使用所有小写字母“小于”所有大写字母或类似内容的排序。这只是扩展了它可以处理的有限令牌集。

    为了概括这个限制——代码将只处理有限的序列标记集，如上面 2. 中所述。另外 - 没有错误处理，所以如果你输入一个带有数字或标点符号的字符串，它将失败。

于 2015-06-16T12:02:33.773 回答
-1

这是最长递增子序列的变体。不同之处在于您的元素是有界的，因为它们只能从“a”运行到“z”。你的算法确实是 O(N)。O(N log N) 是可能的，例如使用上面链接中的算法。可能元素数量的限制将其变为 O(N)。

于 2015-06-16T08:16:27.320 回答