解法1 逐字检查

解法思路：

将词1中的字符逐个到词2中检查是否存在，存在就打勾标记（防止重复检查）。如果每个字符都能找到，则两个词是变位词。只要有一个字符找不到，就不是变位词。 实现打勾标记：将词2对应字符设为None,由于字符串是不可变类型，需要先复制到列表中。

#判断两个词是否为变位词 def anagramSolution(s1,s2): alist=list(s2) pos1=0 stillOK=True while pos1<len(s1) and stillOK:#循环s1中的每个字符 pos2=0 found=False while pos2<len(alist) and not found:#对s2逐个对比 if s1[pos1]==alist[pos2]: found=True else: pos2=pos2+1 if found: alist[pos2]=None#若找到将其变为None else: stillOK=False#未找到失败 pos1=pos1+1 return stillOK print(anagramSolution('abcd','dcba')) print(anagramSolution('python','cython'))

时间复杂度分析

解法2 排序比较

解法思路：

将两个字符串都按照字母顺序排好序，再逐个字符对比是否相同，如果相同则是变位词，有任何不同就不是变位词。

#解法2 ：判断两个词是否为变位词 def anagramSolution(s1,s2): alist1=list(s1) alist2=list(s2) alist1.sort() alist2.sort() pos=0 stillOK=True while pos<len(s1) and stillOK: if alist1[pos]==alist2[pos]: pos=pos+1 else: stillOK=False return stillOK print(anagramSolution('abcd','dcba')) print(anagramSolution('python','cython'))

时间复杂度分析

解法3 计数比较

解法思路：

对比两个词中每个字母出现的次数，如果26个字母出现的次数都相同，这两个字符串一定为变位词。

具体做法：

为每个词设置一个26位的计数器，先检查每个词，在计算其中设定好每个自出出现的次数。计数完成后，进入比较阶段，看两个字符串的计数器是否相同，如果相同则是变位词。

#解法3 计数比较 def anagramSolution(s1,s2): counter1=[0]*26 counter2=[0]*26 #对字符串s1和s2分别计数 for i in range(len(s1)): pos1=ord(s1[i])-ord('a') counter1[pos1]=counter1[pos1]+1#ord()返回字符对应的ASCII码值 for j in range(len(s2)): pos2=ord(s2[j])-ord('a') counter2[pos2]=counter2[pos2]+1#ord()返回字符对应的ASCII码值 stillOK=True pos=0 #对两个计数器内容进行比较 while pos<26 and stillOK: if counter1[pos]==counter2[pos]: pos=pos+1 else: stillOK=False return stillOK print(anagramSolution('abcd','dcba')) print(anagramSolution('python','cython'))

时间复杂度分析