Hackerrank Python哈希表：赎金通知因超时而终止：(

Question

Hackerrank哈希表遇到“由于超时而终止”错误：21个测试用例中有6个的赎金注释

实现了开放地址哈希。输入字符串的大小高达30000个字符串：我们尝试过将哈希表大小从60000改为300000，但没有成功。你知道吗

CAPACITY = 300000
hashTable = [None] * CAPACITY

def checkMagazine(magazine, note):
    # Store Magazine into hashtable
    for element in magazine:
        # print("STORED " + element)
        position = calculateHash(element)
        # print(position)
        if hashTable[position] == None:
            hashTable[position] = element
            # print("Stored into " + str(position))
        else:
            i = 1
            # print("collided into " + str((position) % CAPACITY))
            while hashTable[(position + i) % CAPACITY] != None:
                # print("collided into " + str((position + i) % CAPACITY))
                i += 1
            hashTable[(position + i) % CAPACITY] = element


    # Check if all items in note is in hashtable
    included = True
    for item in note:
        position = calculateHash(item)
        if hashTable[position] != item:
            i = 1
            while hashTable[(position + i ) % CAPACITY] != item:
                if hashTable[(position + i ) % CAPACITY] == None:
                    included = False
                    print("No")
                    return
                else:
                    i += 1
            hashTable[(position + i ) % CAPACITY] = "DONED"
        else:
            hashTable[position] = "DONED"
        # print("Found " + item)            


    print("Yes") 

def calculateHash(string):
    return hash(string) % CAPACITY

假设哈希表是解决这个问题的最佳方法（时间复杂度O（n）），那么发生超时的原因是因为开放地址哈希吗？还是另有原因？你知道吗

Answer 1

应该试一下这样的方法：

magazine = 'two times three is not four'
note = 'two times two is four'

if set(magazine.split()) & set(note.split()) == set(note.split()) :
    print 'yes'
else :
    print 'no'

你可以通过预先计算set(note.split())来节省一些时间，但我怀疑它是否很大。你知道吗

如果您关心字数，可以使用Counter：

from collections import Counter

然后检查便笺中的每个字，计数器比杂志中同一个字的计数器小。你知道吗

Answer 2

我认为这个问题与你的执行有关。如果你传递一个大的“杂志”输入，比如["a", "a", "a", .... "a"]，看看你的代码会发生什么。你知道吗