《Python数据结构与算法分析》第二弹《2.2.2 异序词检测示例》

2.2.2 异序词检测示例

要展示不同数量级的算法，一个好例子就是经典的异序词检测问题。如果一个字符串只是重排了另一个字符串的字符，那么这个字符串就是另一个的异序词，比如heart与earth，以及python与typhon。为了简化问题，假设要检查的两个字符串长度相同，并且都是由26个英文字母的小写形式组成的。我们的目标是编写一个布尔函数，它接受两个字符串，并能判断它们是否为异序词。

1．方案1：清点法清点第1个字符串的每个字符，看看它们是否都出现在第2个字符串中。如果是，那么两个字符串必然是异序词。清点是通过用Python中的特殊值None取代字符来实现的。但是，因为Python中的字符串是不可修改的，所以先要将第2个字符串转换成列表。在字符列表中检查第1个字符串中的每个字符，如果找到了，就替换掉。

2．方案2：排序法尽管s1与s2是不同的字符串，但只要由相同的字符构成，它们就是异序词。基于这一点，可以采用另一个方案。如果按照字母表顺序给字符排序，异序词得到的结果将是同一个字符串。代码清单2-7给出了这个方案的实现代码。在Python中，可以先将字符串转换为列表，然后使用内建的sort方法对列表排序。

4．方案4：计数法最后一个方案基于这样一个事实：两个异序词有同样数目的a、同样数目的b、同样数目的c，等等。要判断两个字符串是否为异序词，先数一下每个字符出现的次数。因为字符可能有26种，所以使用26个计数器，对应每个字符。每遇到一个字符，就将对应的计数器加1。最后，如果两个计数器列表相同，那么两个字符串肯定是异序词。

一、算法文件 anagram.py

def anagramSolution1(s1,s2):
    """
    方法1：清点法
    """
    # 首先检查长度是否相同
    if len(s1) != len(s2):
        return False
        
    alist = list(s2)

    pos1 = 0
    stillOK = True

    while pos1 < len(s1) and stillOK:
        pos2 = 0
        found = False
        while pos2 < len(alist) and not found:
            if s1[pos1] == alist[pos2]:
                found = True
            else:
                pos2 = pos2 + 1
        if found:
            alist[pos2] = None
        else:
            stillOK = False

        pos1 = pos1 + 1

    return stillOK

def anagramSolution2(s1,s2):
    """
   方法2： 排序法
    """
    # 首先检查长度是否相同
    if len(s1) != len(s2):
        return False
        
    alist1 = list(s1)
    alist2 = list(s2)

    alist1.sort()
    alist2.sort()

    pos = 0
    matches = True

    while pos < len(s1) and matches:
        if alist1[pos] == alist2[pos]:
            pos = pos +1
        else:
            matches = False
    return matches

def anagramSolution4(s1,s2):
    """
   方法4 ： 计数法
    """
    # 首先检查长度是否相同
    if len(s1) != len(s2):
        return False
        
    # 检查是否都是小写字母
    if not s1.islower() or not s2.islower():
        return s1 == s2
        
    c1 = [0] * 26
    c2 = [0] * 26

    for i in range(len(s1)):
        pos = ord(s1[i]) - ord('a')
        if 0 <= pos < 26:
            c1[pos] = c1[pos] + 1

    for i in range(len(s2)):
        pos = ord(s2[i]) - ord('a')
        if 0 <= pos < 26:
            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

 二、测试代码 test_anagram.py

from anagram import anagramSolution1, anagramSolution2, anagramSolution4

# 测试用例
test_cases = [
    ('listen','silent',True),
    ('python','typhon',True),
    ('Hello','word',False),
    ('aab','abb',False),
    (' ',' ',True),
    ('abc','abcd',False),
]

# 测试函数
def test_all_methods():
    print("开始测试所有方法...")
    print("{:<15} {:<15} {:10} {:<10} {:<10} ".format("字符串1","字符串2","清点法","排序法","字典法"))
    
    for s1,s2, expected in test_cases:
        r1 = anagramSolution1(s1,s2)
        r2 = anagramSolution2(s1,s2)
        r4 = anagramSolution4(s1,s2)

        print("{:<15} {:<15} {:10} {:<10} {:<10}".format(s1,s2,str(r1),str(r2),str(r4)))

        # 验证结果是否正确
        assert r1 == expected
        assert r2 == expected
        assert r4 == expected

    print('所有测试通过！')

# 运行测试
if __name__ == '__main__':
    test_all_methods()

 

测试结果

开始测试所有方法...
字符串1            字符串2            清点法        排序法        字典法
listen          silent          True       True       True
python          typhon          True       True       True
Hello           word            False      False      False
aab             abb             False      False      FalseTrue       True       True
abc             abcd            False      False      False
所有测试通过！