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