"变位词"判断问题

问题描述

• 所谓变位词是指两个词之间存在组成字母的重新排列关系
• 如：heart和earth，python和typhon
• 为了简单起见，假设参与判断的两个词仅由小写字母组成，而且长度相等

解题目标：

写一个bool函数，以两个词作为参数，返回这两个词是否变位词
可以很好的展示同一问题的不同数量级解法

解法1：逐字检查

解法思路

将词1中的字符逐个到词2中检查是否存在，存在就“打钩”标记（防止重复检查）。如果每个字符都能找到，则两个词是变位词，只要有1个字符找不到，就不是变位词。

程序技巧

实现“打钩”标记：将词2对应字符设为None，由于字符串是不可变类型，需要先复制到列表中

代码

def bianweici(s1, s2):
    alist = list(s2)  #复制s2到列表
    stillOk = True
    i1 = 0
    while i1 < len(s1) and stillOk: #循环s1的每个字符
        found = False
        i2 = 0
        while i2 < len(alist) and not found:
            if s1[i1] == alist[i2]:   #在s2逐个对比
                found = True 
            else:
                i2 += 1
        if found:
            alist[i2] = None    #找到，打钩
        else:
            stillOk = False     #未找到，失败
        i1 += 1
    return stillOk
print(bianweici('python', 'typhon'))
print(bianweici('abcd', 'bcae'))

算法分析

• 问题规模：词中包含的字符个数n
• 主要部分在于两重循环
  • 外层循环遍历s1每个字符，将内循环执行n次，而内循环在s2中查找字符，每个字符的对比次数，分别是1,2...n中的一个，而且各不相同
• 所以总的执行次数是1+2+3+...+n
  • 可知其数量级为O(n²)

解法2：排序比较

解题思路

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

代码

def bianweici(s1, s2):
    alist1 = list(s1)
    alist2 = list(s2)  #转为列表
    alist1.sort()
    alist2.sort()       #分别排序
    i = 0
    matches = True
    while i < len(alist1) and matches:
        if alist1[i] == alist2[i]:   #逐个比对
            i += 1
        else:
            matches =False
    return matches

算法分析

• 粗看上去，本算法只有一个循环，最多执行n次，数量级是O(n)
  • 但循环前面的两个sort并不是无代价的
  • 排序算法采用不同的解决方案，其运行时间数量级差不多是O(n²)或者是O(n*log n)，大过循环的O(n)
• 所以本算法时间主导的步骤是排序步骤
• 本算法的运行时间数量级就等于排序过程的数量级O(n*log n)

解法3：计数比较

解题思路

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

具体做法

• 为每个词设置一个26位的计算器，先检查每个词，在计数器中设定好每个字母出现的次数
• 计算完成后，进入比较阶段，看两个字符串的计数器是否相同，如果相同则输出是变位词的结论

代码

def bianweici(s1, s2):
    c1 = [0] * 26
    c2 = [0] * 26
    for i in range(len(s1)):  #分别计数
        pos = ord(s1[i]) - ord('a')
        c1[pos] += 1
    for i in range(len(s2)):
        pos = ord(s2[i]) - ord('a')
        c2[pos] += 1
    i = 0
    flag = True
    while i < 26 and flag:  #计数器比较
        if c1[i] == c2[i]:
            i += 1
        else:
            flag = False
    return flag

算法分析

• 计数比较算法中有3个循环迭代，但不像解法1那样存在嵌套循环
  • 前两个循环用于对字符串进行计数，操作次数等于字符串长度n
  • 第3个循环用于计数器比较，操作次数总是26次
• 所以总操作次数T(n)=2n+26，其数量级为O(n)
  • 这是一个线性数量级的算法，是3个变位词判断算法中性能最优的
• 值得注意的是，本算法依赖于两个长度为26的计数器列表，来保存字符计数，这相比前三个算法需要更多的存储空间
• 牺牲存储空间来换取运行时间，或者相反，这种在时间空间之间的取舍和权衡，在选择问题解法的过程中经常会出现。

PS：可以尝试用字典改写解法3