判断两个词是否为易位构词（anagram）

两个词是否为易位构词（anagram）"/>

判断两个词是否为易位构词（anagram）

文章目录

• 题目
• 解答思路一 ：逐个检查
• 时间复杂度 O(n^2)
• 解答思路二 ：排序并比较
• 时间复杂度 O(n^2)或O(nlogn)
• 解答思路三 ：暴力破解
• 时间复杂度 O(n!)
• 解答思路四 ：利用字母出现的次数
• 时间复杂度 O(n)

题目

易位同构词是指，一个词是另一个词的字母重排列，比如"heart"和"earth","python"和"typhon"均互为易位同构词。我们的目标是写一个判断函数，参数是两个字符串，函数返回它们是不是易位同构词。

解答思路一 ：逐个检查

首先检查字符串的长度，然后查看第一个字符串中的每个字母是否出现在第二个字符串中。如果能遍历完，说明这两个字符串是易位同构词。另外，由于可能会出现重复字母的情况，所以对第二个字符串中检查过的字符都标记为None。

def anagramSolution1(s1,s2):if len(s1) != len(s2):  # 若长度不等，返回falsestillOK = Falsealist = list(s2)  # 把s2表示成一个列表pos1 = 0stillOK = Truewhile pos1 < len(s1) and stillOK:  # 遍历s1pos2 = 0found = Falsewhile pos2 < len(alist) and not found:  # 遍历s2中的元素# 在s2中找到一个和s1[pos1]相等的元素时，found=True，循环结束if s1[pos1] == alist[pos2]:  found = Trueelse:pos2 = pos2 + 1if found:  # 把s2中和s1[pos1]相等的元素置为Nonealist[pos2] = Noneelse:stillOK = Falsepos1 = pos1 + 1return stillOKprint(anagramSolution1('abcd','dcba'))

时间复杂度 O(n^2)

s1中的每个字符，都会导致s2中最多n个字符的迭代，所以时间复杂度是
∑ i = 1 n i = n ( n + 1 ) 2 = 1 2 n 2 + 1 2 n \sum_{i=1}^n i=\frac{n(n+1)}{2}=\frac{1}{2}n^2+\frac{1}{2}n i=1∑n​i=2n(n+1)​=21​n2+21​n
也就是 O ( n 2 ) O(n^2) O(n2)

解答思路二 ：排序并比较

虽然两个字符串不同，但包含的字母是相同的，所以可以先分别进行排序，然后再在每个位置上进行比较。

def anagramSolution2(s1,s2):alist1 = 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 = Falsereturn matchesprint(anagramSolution2('abcde','edcba'))

时间复杂度 O(n^2)或O(nlogn)

这种方法乍看之下似乎是 O ( n ) O(n) O(n)的时间复杂度，因为只经过了一次遍历。但是，在排序部分是有时间复杂度的，而排序才是决定算法整体时间复杂度的因素。所以，本算法的时间复杂度，也就是排序算法的时间复杂度一般为 O ( n 2 ) O(n^2) O(n2)或 O ( n l o g n ) O(nlogn) O(nlogn)

解答思路三 ：暴力破解

因为s1和s2只是字母排列组合不同，所以可以对s1列举出所有重排列的方法，然后在这些方法中寻找是否有s2的存在。

时间复杂度 O(n!)

这里的时间复杂度是 O ( n ! ) O(n!) O(n!)

解答思路四 ：利用字母出现的次数

在s1中出现的字母及其次数，和s2中出现的字母及其次数是一样的，所以可以先统计两个字符串中出现的字母及其次数，然后进行比较。

def anagramSolution4(s1,s2):c1 = [0]*26c2 = [0]*26for i in range(len(s1)):pos = ord(s1[i])-ord('a')c1[pos] = c1[pos] + 1for i in range(len(s2)):pos = ord(s2[i])-ord('a')c2[pos] = c2[pos] + 1'''这一段等同于下面的代码for k in range(26):if c1[k]!=c2[k]:stillOK=Falsebreakreturn stillOK'''j = 0stillOK = Truewhile j<26 and stillOK:if c1[j]==c2[j]:j = j + 1else:stillOK = Falsereturn stillOKprint(anagramSolution4('apple','pleap'))

时间复杂度 O(n)

前面的两次迭代是基于 O ( n ) O(n) O(n)的时间复杂度，第三次迭代的时间是
T ( n ) = 2 n + 26 T(n)=2n+26 T(n)=2n+26，所以一共是 O ( n ) O(n) O(n)的时间复杂度。
但是这个算法需要额外的空间来保存两个字符串的计数列表，所以是牺牲空间来换时间。

参考：
AnAnagramDetectionExample