乱序字符串检查
Andy 2020-02-18
学习笔记
Python
数据结构
# 解法2：排序和比较
# 解法2：排序和比较
def anagramSolution2(s1, s2):
alist1 = list(s1)
alist2 = list(s2)
alist1.sort()
alist2.sort()
pos = 0
matches = True
while pos < len(s1) and matches:
if alist1[pos] == alist2[pos]:
pos = pos + 1
else:
matches = False
return matches
print(anagramSolution2('abcde', 'edcba'))
>>>True
排序通常是 O(n^2)O(n2) 或 O(nlogn)O(nlogn)。所以排序操作比迭代花费更多。最后该算法跟排序过程有同样的量级。
# 解法3：计数和比较
def anagramSolution3(s1, s2):
c1 = [0] * 26
c2 = [0] * 26
for i in range(len(s1)):
pos = ord(s1[i]) - ord('a')
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 = j + 1
else:
stillOK = False
return stillOK
print(anagramSolution3('apple', 'pleap'))
>>>True
这个方案有多个迭代，但是和第一个解法不一样，它不是嵌套的。两个迭代都是 n, 第三个迭代，比较两个计数列表，需要 26 步，因为有 26 个字母。一共 T(n)=2n+26，即 O(n)，我们找到了一个线性量级的算法解决这个问题。
虽然最后一个方案在线性时间执行，但它需要额外的存储来保存两个字符计数列表。换句话说，该算法牺牲了空间以获得时间。