美文网首页
数据结构与算法Python:判断变位词的四种实现算法和比较

数据结构与算法Python:判断变位词的四种实现算法和比较

作者: 金融测试民工 | 来源:发表于2020-03-21 14:39 被阅读0次

问题描述:

    所谓的‘变位词’指的是两个词之间存在字母的重新排列关系,如heart和earth,python和typhon。

解题目标:

    写一个bool函数,以两个词作为参数,返回这两个词是否为变位词。

解法1:逐字检查

解题思路:

    将词1中的字符逐个到词2中检查是否存在,存在着打勾☑️标记(防止重复检查),如果每个字符都能找到,则两个词是变位词,而只要有一个字符找不到,就不是变位词。

逐字检查

代码实现如图:

法1代码

该算法主要部分有两重循环,因此时间复杂度为\omicron (n^2 )

法2:排序比较

解题思路:

    将两个字符串都按照字母顺序排好序,再逐个字符对比是否相同,如果相同则为变位词,有任何不同就不是。

排序比较

代码实现如图:

法2代码

该算法粗看上去只有一个循环,复杂度为O(n),但是循环前面的两个sort并不是无代价的,其时间复杂度差不多是\omicron (x_{}^2 )或者\omicron (nlogn),大于循环的O(n),所以该算法的时间复杂度等于排序过程的时间复杂度o(nlogn)。

法3:暴力法

解题思路:

    穷尽所以可能组合,将s1字符进行全排列,看s2是否出现在全排列的列表中。

暴力法

但是暴力法时间复杂度为O(n!),因此暴力法不是好算法,会非常慢。

法4:技术比较法

解题思路:

    对比两个词中每个字母出现的次数,如果26个字母出现的次数都相同,则两个字符串就一定是变位词。需要为每个词设置一个26位的计数器,在计数器中设定好每个字母出现的次数。

代码实现如图:

法4代码

    该方法有3个循环迭代,但不像法1那样存在嵌套循环,三个循环的操作次数都是26次。其时间复杂度为O(n),但是本算法依赖两个长度为26的计数器列表来保存字符计数器,因此比前三个算法需要更多的存储空间,这是用存储空间换取时间的算法。

相关文章

网友评论

      本文标题:数据结构与算法Python:判断变位词的四种实现算法和比较

      本文链接:https://www.haomeiwen.com/subject/ymmyyhtx.html