字母易位词的判断

字母易位词的判断"/>

字母易位词的判断

方法一：枚举法

def anagramSolution1(s1,s2):if len(s1) != len(s2):return Falsealist = list(s2)   #python中字符串不可改变，复制到一个新的列表中pos1 = 0stillOK = Truewhile pos1 < len(s1) and stillOK:pos2 = 0found = Falsewhile pos2 < len(alist) and not found:if s1[pos1] == alist[pos2]:found = Trueelse:pos2 = pos2 + 1if found:alist[pos2] = Noneelse:stillOK = Falsebreakpos1 = pos1 + 1return stillOKprint(anagramSolution1('abcd','dcba'))

方法二：先排序，再对比字符串

#此种算法的复杂度即为O(n*logn+n)，为O(n*logn)
def anagramSolution2(s1,s2):if len(s1) != len(s2):return Falsealist1 = list(s1)alist2 = list(s2)alist1.sort()alist2.sort()pos = 0matches = Truewhile pos < len(s1) and matches:if alist1[pos]==alist2[pos]:pos = pos + 1else:matches = Falsebreakreturn matches# print(anagramSolution2('abcde','edcba'))

方法三：设置26个计数器，然后判断对应位置的计数是否相等

# 我们可以为字符串s1和s2分别设置26个计数器，然后判断这对应位置的计数是否相等
# 如果对应计数完全相等，则为字母易位词。
# 总操作次数为T(N)=2n+26,其数量级为O（n)。需要比前两种更多的储存空间
def anagramSulutions3(s1,s2):c1 = [0] * 26c2 = [0] * 26for i in range(len(s1)):pos = ord(s1[i]) - ord('a') #ord将字母转换成对应的ASCII码c1[pos] = c1[pos] + 1print(c1)print('-' * 30)for i in range(len(s2)):pos = ord(s2[i]) - ord('a')c2[pos] = c2[pos] + 1print(c2)print('-' * 30)print(c1,c2)j = 0stillOK = Truewhile j <26 and stillOK:if c1[j] == c2[j]:j += 1else:stillOK = Falsereturn stillOKprint(anagramSulutions3('abcde','bcade'))

方法三结果图