[TOC]
“变位词”判断问题
问题描述
所谓“变位词”是指两个词之间存在组成字母的重新排列关系
如：heart和earth，Python和typhon
为简单起见，假设参与判断的两个词仅由小写字母构成，而且长度相等
解题目标
写一个bool函数，以两个词作为参数，返回这两个词是否是变位词
解法一：逐字检查
解法思路
将词1中的字符逐个到词2中检查是否存在，存在就”打勾“标记（防止重复）
如果每个字符都能找到，那么这2个词就是变位词，只要有一个字符没有找到，就不是变位词
程序技巧
实现”打勾“标记：将词2对应字符设为None
由于字符串是不可变类型，需要先复制到列表中
代码
def abc(s1,s2):
s2_list=list(s2) # str转换为list
pos1=0
stillok = True
while pos1<len(s1) and stillok: # 循环s1长度的次数
pos2=0
found = False
while pos2<len(s2_list) and not found: # 循环s2长度的次数
if s1[pos1]==s2_list[pos2]:
found=True
else:
pos2=pos2+1
if found:
s2_list[pos2] = None
else:
stillok=False
pos1 = pos1+1
return stillok
if __name__ == "__main__":
zzz = abc("abcd","dcba")
print(zzz)解法二：排序比较
解题思路
- 将2个字符串先排序
- 对比是否相等
程序技巧
- str转list
- 进行排序
- list转str
- 进行比较
def Method2(s1,s2):
# 字符串是不可变的无法排序，str转list
list1=list(s1)
list2=list(s2)
# 进行排序
list1.sort()
list2.sort()
# list 转 str
a = ''.join(list1)
b = ''.join(list2)
# 进行比较
if a==b:
return True
else:
return False
if __name__ == "__main__":
zzz2 = Method2('ablc','lcab')
print(zzz2)解法三：暴力法
解题思路
就是穷尽所有可能的组合
然后将s1中出现的字符进行全排序，再查看s2是否出现在全排列的列表中
这里就不附代码了，暴力法在这里恐怕不是一个好的算法
解法四：计数比较
解题思路
对比两个词中每个字符出现的次数，如果26个字母出现的次数都相同的话，那么这2个就是变位词
程序技巧
def Method4(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
stillok =True
j=0
while stillok and j<26:
if c1[j]!=c2[j]:
stillok=False
j+=1
return stillok
if __name__ == "__main__":
zzz4 = Method4('ablc','lcab')
print(zzz4)这个是四个解法中，性能最优的，T(n)=2n+26
这个解法中依赖额是2个长度为26的计数器列表，来保存字符计数，所以相对于之前3个算法来说，就需要了更多的空间，这里就是用空间换取了时间
