python - 可能具有最佳时间复杂度的字母汤问题

Question

我得到了以下问题(字母汤)作为我的数据结构类(class)练习。

https://github.com/kennedyCzar/AlphabetSoup-Using-Django

我在 O(m+s) 中解决了这个问题，其中 m 是消息的长度，s 是汤的长度(我刚刚从汤创建了一个表，并决定是否可以使用它创建消息表)

def checkBowl(message, soup):
  d = {}

  # O(S)
  for c in soup:
    d[c] = d.get(c, 0) + 1

  # O(m)
  for c in message:
    if(d.get(c, 0) == 0):
      return False
    else:
      d[c] -= 1

  # So the overall time complexity is O(m+s)
  return True

但似乎给定的 GitHub 在 O(mlogm) 中解决了它，但是我认为他/她的解决方案是在 O(m*s) 中，因为他/她只是没有考虑 python 的 in 运算符在 O(长度列表)。

顺便问一下，有人可以提示一下，是否可以用更好的时间复杂度来解决这个问题？ (问题指定这碗汤可能很大)

Answer 1

正如您所说，对于消息中的每个字母，链接算法都会迭代汤以找到该字母。如果找到这封信，就会将其从汤中取出。因此时间复杂度为O(m * S) .

您的算法是O(m + S)因为你只对汤迭代一次。所以你的解决方案更好。

但是如果汤很大怎么办？无限量的汤怎么样？如果汤是一个无限的生成器，即使汤的第一个字母就是消息本身，您也永远无法完成字典的构建。

这引出了一个想法:为什么不迭代汤的字母，直到获得消息的字母？在这种情况下，您将阅读信件，直到能够写出消息为止，并在消息完成后立即停止:

import collections

def check_bowl2(message, soup):
    # O(m)
    message_letters = collections.Counter(message)

    # O(S)
    for c in soup:
        if c not in message_letters: # we don't need `c`
            pass
        elif message_letters[c] == 1:
            del message_letters[c] # we won't need `c` anymore
            if not message_letters: # we found all letters
                return True
        else: # we still need `c`, but one less time
            message_letters[c] -= 1

    return False

时间复杂度依然是O(m + S) ，但空间复杂度降低:O(m)与 O(S) 。当然，如果您要在同一个汤中查找许多消息，构建字典仍然是最好的选择。

我认为您不会找到比 O(S) 更快的算法:在最坏的情况下(消息不存在)，您必须至少迭代整个汤一次。