python数据结构与算法 变位词

变位词

问题简述

“变位词”判断问题:所谓 "变位词" 是指两个词之间存在组成字母的重新排列关系,例如 Heart 和 Earth,python 和 typhon,为了简单起见,假设参与判断的两个词仅由小写字母组成,而且长度相等

解题目标

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

意义

​ 用于展示解决统一问题的不同数量级的算法的差距

解法一:逐字检查

​ 假设要检查的字符串记为 A 和 B,一个很显然的思路是把 A 中的每一个字符都到 B 中去检查看是否存在,如果存在就“打勾”(以防重复检查),如果每个字符都能找到,则两个词是变位词,但凡有 1 个字符找不到,就不是变位词

​ 思路很简单,但这里面有个小细节:应该如何实现“打勾”呢?其实很简单,只需要给抹掉,下一次就不会再检索到它了,然而字符串并非可变类型,所以我们需要 list 来做中转,下面给出具体实现和详细注释:

def anagramSolution(s1,s2):
    s_list = list(s2)    # 将第二个字符串转为可变类型list
    pos1 = 0            # 用来遍历第一个字符串的指针
    stillOk = True        # 只要有一个没找到,就不是变位词
    while pos1 < len(s1) and stillOk:    # 因为s1和s2的长度一定是一样的,所以直接遍历s1
        pos2 = 0        #遍历第二个列表字符串的指针
        found = False    # 一开始当然是什么都没有找到
        while pos2 < len(s_list) and not found:    # 拿着s1的第一个元素检查s2中的每一个
            if s1[pos1] == s_list[pos2]:    #如果发现一样的元素
                found = True                #说明找到了一个
            else:                            # 如果没找到
                pos2 = pos2 + 1                # 看下一个
        if found:                            # 如果找到了
            s_list[pos2] = None                # 抹掉
        else:                                # 但凡有一个没找到
            stillOk = False                    # 就不需要继续了
        pos1 = pos1 + 1                        # 取出s1中的下一个元素继续检查s2
    return stillOk                            # 返回结果

解法一:算法分析

问题的规模:

​ 词中包含的字符个数 n

最耗时的部分:

​ 两重循环,这里不给出推导过程,数量级为 n 的平方

解法二:排序比较

​ 首先将两个字符串都按照字母顺序排好序,只要构成元素相同,最后排完序的结果一定也是相同的,我们只需要检查两个字符串是否相同就可以了,相同则是变位词,不相同则不是变位词

​ 如何排序?这里我们直接引用 python 中 list 提供的方法sort直接进行排序,它可以直接修改原有的 list

​ 我们来看具体实现,仍然比较简单:

def anagramSolution(s1,s2):
    alist1 = list(s1)    
    alist2 = list(s2)    #先把两个字符串都转化为list
    
    match = True        # 用来检查两个list是否相同
    pos = 0                # 同步检测两个list的对应位置
    
    alist1.sort()        
    alist2.sort()        # 为两个列表排好序
    while pos < len(alist1) and match:    # 这一段是检查两个列表是否完全相同
        if alist1[pos] == alist2[pos]:    
            pos = pos + 1
        else:                            # 只要有一个不相同
            match = False                # 就是不匹配
    return match

解法二:算法分析

​ 可以看到,改进过的算法比原有的方法简洁的多, 那么时间复杂度如何呢?

复杂度分析

​ 粗看过去,改进过的算法似乎只有一个循环,最多执行 n 次

但是 ,在循环之前的两个 sort 并非没有任何代价 ,它的运行时间数量级约为 n 倍的 log n,大于循环所执行的 n

​ 因此,本算法中最耗时的部分应为排序过程,时间复杂度为 n log n

解法三:计数比较

​ 对比两个词中每个字母出现的次数,如果 26 个字母出现的次数都相同的话,这两个字符串一定是变位词

​ 为每个词设置一个 26 位的计数器,先检查每个词,在计数器中设定好每个字母出现的次数

​ 计数器完成后,进入比较阶段,看两个字符串的计数器是否相同,如果相同则输出是变位词的结论

​ 下面给出代码演示:

def anagramSolution(s1,s2):
    c1 = [0]*26
    c2 = [0]*26        #分别设置计数器
    for i in range(len(s1)):
        pos = ord(s1[i])-ord('a')    # ord表示转化为编码,来计算出在计数器中的偏移位置
        c1[pos] = c1[pos] + 1        #对应位置计数器累加
    for i in range(len(s2)):        # 对另一个也做相同的操作
        pos = ord(s2[i])-ord('a')
        c2[pos] = c2[pos]+1
    j = 0                            # 从这里开始比较两个计数器是否相同,和上面的解法一样
    stillOk = True
    while j < 26 and stillOk:
        if c1[j] == c2[j]:
            j = j + 1
        else:
            stillOk = False
    return stillOk

解法三:算法分析

​ 虽然看起来有三个循环,但可以发现并非嵌套的循环,最后一次循环是比较计数器,其时间是固定的,所以算法复杂度是 2n + 26,其数量级为 n,是三个算法中性能最好的

小结

​ 解决相同问题时合理的算法优化可以显著提高性能

    nnnp
    nnnp  2020-03-23, 17:55

    Thank you star