hash算法的应用

a=[1,2,2,1,1,3]
b=['x','y','y','x','x','z']
def word_pattern(a,b):
    #如果a,b长度不一致则直接返回False
    if len(a)!=len(b):
        return False
    #用来存储映射关系
    #例如{1:'x',2:'y',3:'z'}
    hash={}
    #用来存储是否被使用
    #如果a=[1,1,2],b=['x','y','z']
    #那么1:'y'就重复使用了，就返回False
    used={}
    for i in range(len(a)):
        if a[i] in hash:
            #不是第一次出现，检查映射关系是否匹配
            if hash[a[i]]!=b[i]:
                return False
        else:
            #检查这个单词是否使用过，使用过则返回False
            if b[i] in used:
                return False
        hash[a[i]]=b[i]
        used[b[i]]=True
    return True
print(word_pattern(a,b))

a="1123"
b="9111"
def gethint(a,b):
    A=0
    B=0
    a_dict={}
    b_dict={}
    for i in range(len(a)):
        if b[i] == a[i]:
            A+=1
        else:
            if b[i] in b_dict:
                b_dict[b[i]]=b_dict[b[i]]+1
            else:
                b_dict[b[i]]=1
            if a[i] in a_dict:
                a_dict[a[i]] = a_dict[a[i]] + 1
            else:
                a_dict[a[i]]=1
    for digit in b_dict:
        if digit in a_dict:
            B+=min(a_dict[digit],b_dict[digit])
    return str(A)+"A"+str(B)+"B"
print(gethint(a,b))
输出：1A1B

a=["catt","cat","bat","rat",]
b="the cattle was rattled by the battery"
def replacewords(a,b):
    b=b.split(" ")
    for i in a:
        for j in range(len(b)):
            if b[j][:len(i)]==i:
                b[j]=i
    return " ".join(b)
print(replacewords(a,b))

a=["catt","cat","bat","rat",]
b="the cattle was rattled by the battery"
def replacewords(a,b):
    import collections
    b=b.split(" ")
    a_dict=collections.defaultdict(set)
    b_dict=collections.defaultdict(int)
    for w in a:
        a_dict[w[0]].add(w)
        b_dict[w[0]]=max(b_dict[w[0]],len(w))
    print(a_dict,b_dict)
    for i,w in enumerate(b):
        for j in range(b_dict[w[0]]):
            if w[:j+1] in a_dict[w[0]]:
                b[i]=w[:j+1]
                break
    return " ".join(b)