《Python数据结构与算法分析》第二弹《2.2.2 异序词检测示例》-尧图网站建设

📅 发布时间：2026/6/20 23:59:05

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

 1 def anagramSolution1(s1,s2):
 2     """
 3     方法1：清点法
 4     """
 5     # 首先检查长度是否相同
 6     if len(s1) != len(s2):
 7         return False
 8         
 9     alist = list(s2)
10 
11     pos1 = 0
12     stillOK = True
13 
14     while pos1 < len(s1) and stillOK:
15         pos2 = 0
16         found = False
17         while pos2 < len(alist) and not found:
18             if s1[pos1] == alist[pos2]:
19                 found = True
20             else:
21                 pos2 = pos2 + 1
22         if found:
23             alist[pos2] = None
24         else:
25             stillOK = False
26 
27         pos1 = pos1 + 1
28 
29     return stillOK
30 
31 def anagramSolution2(s1,s2):
32     """
33    方法2： 排序法
34     """
35     # 首先检查长度是否相同
36     if len(s1) != len(s2):
37         return False
38         
39     alist1 = list(s1)
40     alist2 = list(s2)
41 
42     alist1.sort()
43     alist2.sort()
44 
45     pos = 0
46     matches = True
47 
48     while pos < len(s1) and matches:
49         if alist1[pos] == alist2[pos]:
50             pos = pos +1
51         else:
52             matches = False
53     return matches
54 
55 def anagramSolution4(s1,s2):
56     """
57    方法4 ： 计数法
58     """
59     # 首先检查长度是否相同
60     if len(s1) != len(s2):
61         return False
62         
63     # 检查是否都是小写字母
64     if not s1.islower() or not s2.islower():
65         return s1 == s2
66         
67     c1 = [0] * 26
68     c2 = [0] * 26
69 
70     for i in range(len(s1)):
71         pos = ord(s1[i]) - ord('a')
72         if 0 <= pos < 26:
73             c1[pos] = c1[pos] + 1
74 
75     for i in range(len(s2)):
76         pos = ord(s2[i]) - ord('a')
77         if 0 <= pos < 26:
78             c2[pos] = c2[pos] + 1
79 
80     j = 0
81     stillOK = True
82     while j < 26 and stillOK:
83         if c1[j] == c2[j]:
84             j = j + 1
85         else:
86             stillOK = False
87     return stillOK

二、测试代码 test_anagram.py

 1 from anagram import anagramSolution1, anagramSolution2, anagramSolution4
 2 
 3 # 测试用例
 4 test_cases = [
 5     ('listen','silent',True),
 6     ('python','typhon',True),
 7     ('Hello','word',False),
 8     ('aab','abb',False),
 9     (' ',' ',True),
10     ('abc','abcd',False),
11 ]
12 
13 # 测试函数
14 def test_all_methods():
15     print("开始测试所有方法...")
16     print("{:<15} {:<15} {:10} {:<10} {:<10} ".format("字符串1","字符串2","清点法","排序法","字典法"))
17     
18     for s1,s2, expected in test_cases:
19         r1 = anagramSolution1(s1,s2)
20         r2 = anagramSolution2(s1,s2)
21         r4 = anagramSolution4(s1,s2)
22 
23         print("{:<15} {:<15} {:10} {:<10} {:<10}".format(s1,s2,str(r1),str(r2),str(r4)))
24 
25         # 验证结果是否正确
26         assert r1 == expected
27         assert r2 == expected
28         assert r4 == expected
29 
30     print('所有测试通过！')
31 
32 # 运行测试
33 if __name__ == '__main__':
34     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
所有测试通过！