"变位词"判断问题
问题描述
- 所谓变位词是指两个词之间存在组成字母的重新排列关系
- 如：
heart和earth，python和typhon - 为了简单起见，假设参与判断的两个词仅由小写字母组成，而且长度相等
解题目标：
写一个bool函数，以两个词作为参数，返回这两个词是否变位词
可以很好的展示同一问题的不同数量级解法
解法1：逐字检查
解法思路
将词1中的字符逐个到词2中检查是否存在，存在就“打钩”标记（防止重复检查）。如果每个字符都能找到，则两个词是变位词，只要有1个字符找不到，就不是变位词。
程序技巧
实现“打钩”标记：将词2对应字符设为None，由于字符串是不可变类型，需要先复制到列表中
代码
def bianweici(s1, s2):
alist = list(s2) #复制s2到列表
stillOk = True
i1 = 0
while i1 < len(s1) and stillOk: #循环s1的每个字符
found = False
i2 = 0
while i2 < len(alist) and not found:
if s1[i1] == alist[i2]: #在s2逐个对比
found = True
else:
i2 += 1
if found:
alist[i2] = None #找到，打钩
else:
stillOk = False #未找到，失败
i1 += 1
return stillOk
print(bianweici('python', 'typhon'))
print(bianweici('abcd', 'bcae'))
算法分析
- 问题规模：词中包含的字符个数n
- 主要部分在于两重循环
- 外层循环遍历s1每个字符，将内循环执行n次，而内循环在s2中查找字符，每个字符的对比次数，分别是1,2...n中的一个，而且各不相同
- 所以总的执行次数是1+2+3+...+n
- 可知其数量级为O(n2)
解法2：排序比较
解题思路
- 将两个字符都按照字母顺序排好序
- 再逐个字符对比是否相同，如果相同则是变位词
- 有任何不同就不是变位词
代码
def bianweici(s1, s2):
alist1 = list(s1)
alist2 = list(s2) #转为列表
alist1.sort()
alist2.sort() #分别排序
i = 0
matches = True
while i < len(alist1) and matches:
if alist1[i] == alist2[i]: #逐个比对
i += 1
else:
matches =False
return matches
算法分析
- 粗看上去，本算法只有一个循环，最多执行n次，数量级是O(n)
- 但循环前面的两个sort并不是无代价的
- 排序算法采用不同的解决方案，其运行时间数量级差不多是O(n2)或者是O(n*log n)，大过循环的O(n)
- 所以本算法时间主导的步骤是排序步骤
- 本算法的运行时间数量级就等于排序过程的数量级O(n*log n)
解法3：计数比较
解题思路
对比两个词中每个字母出现的次数，如果26个字母出现的次数都相同的话，这两个字符串就一定是变位词
具体做法
- 为每个词设置一个26位的计算器，先检查每个词，在计数器中设定好每个字母出现的次数
- 计算完成后，进入比较阶段，看两个字符串的计数器是否相同，如果相同则输出是变位词的结论
代码
def bianweici(s1, s2):
c1 = [0] * 26
c2 = [0] * 26
for i in range(len(s1)): #分别计数
pos = ord(s1[i]) - ord('a')
c1[pos] += 1
for i in range(len(s2)):
pos = ord(s2[i]) - ord('a')
c2[pos] += 1
i = 0
flag = True
while i < 26 and flag: #计数器比较
if c1[i] == c2[i]:
i += 1
else:
flag = False
return flag
算法分析
- 计数比较算法中有3个循环迭代，但不像解法1那样存在嵌套循环
- 前两个循环用于对字符串进行计数，操作次数等于字符串长度n
- 第3个循环用于计数器比较，操作次数总是26次
- 所以总操作次数T(n)=2n+26，其数量级为O(n)
- 这是一个线性数量级的算法，是3个变位词判断算法中性能最优的
- 值得注意的是，本算法依赖于两个长度为26的计数器列表，来保存字符计数，这相比前三个算法需要更多的存储空间
- 牺牲存储空间来换取运行时间，或者相反，这种在
时间空间之间的取舍和权衡，在选择问题解法的过程中经常会出现。
