问题描述:
所谓的‘变位词’指的是两个词之间存在字母的重新排列关系,如heart和earth,python和typhon。
解题目标:
写一个bool函数,以两个词作为参数,返回这两个词是否为变位词。
解法1:逐字检查
解题思路:
将词1中的字符逐个到词2中检查是否存在,存在着打勾☑️标记(防止重复检查),如果每个字符都能找到,则两个词是变位词,而只要有一个字符找不到,就不是变位词。

代码实现如图:

该算法主要部分有两重循环,因此时间复杂度为
法2:排序比较
解题思路:
将两个字符串都按照字母顺序排好序,再逐个字符对比是否相同,如果相同则为变位词,有任何不同就不是。

代码实现如图:

该算法粗看上去只有一个循环,复杂度为O(n),但是循环前面的两个sort并不是无代价的,其时间复杂度差不多是或者
,大于循环的O(n),所以该算法的时间复杂度等于排序过程的时间复杂度o(nlogn)。
法3:暴力法
解题思路:
穷尽所以可能组合,将s1字符进行全排列,看s2是否出现在全排列的列表中。

但是暴力法时间复杂度为O(n!),因此暴力法不是好算法,会非常慢。
法4:技术比较法
解题思路:
对比两个词中每个字母出现的次数,如果26个字母出现的次数都相同,则两个字符串就一定是变位词。需要为每个词设置一个26位的计数器,在计数器中设定好每个字母出现的次数。
代码实现如图:

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