- 什么是变位词
两个词之间存在得组成字母重新排列关系，用bool类型返回是否是变位词。如python和typhon
- 解法
1.逐字比较
#s1和s2依次遍历比较 def anagramSulution1(s1,s2): alist = list(s2) #将s2复制成list pos1 = 0 stillOK = True while pos1< len(s1) and stillOK: #循环s1每个字符 pos2 = 0 found = False while pos2 < len(alist) and not found: #s2与s1逐个对比 if s1[pos1] = alist[pos2]: found = True else: pos2 += 1 if found: alist[pos2] = None #找到，将s2对应位置赋值为None else: stillOK = False #未找到 pos1 += 1 return stillOK ###算法复杂度O（n2）
2.排序比较
#将两个字符按照字母顺序排序后按照位置比较
def anagramSulutions(s1,s2):
alist1 = list(s1)
alist2 = list(s2)
alist1.sort() #排序具有时间复杂度(O(nlog n))
alist2.sort()
mathes =True
pos = 0
while pos < len(s1) and mathes:
if alist1[pos] == alist2[pos]
pos += 1
else:
mathes = False
return mathes
print(anagramSulutions('abcde','bcade'))
##算法复杂度O(nlog n),关键在于sort函数的时间复杂度
3. 计数比较
#解决思路:对比每个字母出现的次数，为每个字母设定一个计数器
def anagramSulutions(s1,s2):
c1 = [0] * 26
c2 = [0] * 26
for i in range(len(s1)):
pos = ord(s1[i] - ord('a')) #ord将字母转换成对应的ASCII码
c1[pos] = c1[pos] + 1
for i in range(len(s2)):
pos = ord(s2[i] - ord('a'))
c2[pos] = c2[pos] + 1
j = 0
stillOK = True
while j <26 and stillOK:
if c1[j] == c2[j]:
j += 1
eles:
stillOK = False
return stillOK
print(anagramSulutions('abcde','bcade'))
##时间复杂度T(n) = 2n+26
##时间复杂度为O(n)，但空间复杂度高