两个单词中如果一个是另一个的反转, 则二者被称为是 ‘‘反转词对’’。 编写一个函数,找出单词表中所有的反转词对。
解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| def read_word1(file_in): #来自10.9
word_list = []
for line in file_in:
word = line.strip()
word_list.append(word)
return word_list
def in_bisect(t,a): #来自10.10
"""列表t，单词a，看单词是否在列表内，在的话返回单词的位置。
列表里的单词，必须是已经按字母顺序排好序的。
"""
s1 = int((len(t))/2)
s = s1 #如果a在t内，s保存a的序数
while s1 > 0:
if a == t[s1]:
return s
elif a > t[s1]:
t = t[s1:]
s1 = int(len(t)/2) #在循环过程中，确保s和s1所指的是同一个元素。
#print(a,"的位置大于",s)
s += s1
else:
t = t[:s1]
s1 = int(len(t)/2)
#print(a,"的位置小于等于",s)
s -= s1
return None
def findpairs(word_li):
i = 0
for word in word_li:
drow = word[::-1] #将单词里的字母按照相反的顺序排列
k = in_bisect(word_li[i:],drow) #写word_list[i:]目的是不让程序往前去找所谓的“反转词”
if k:
print(word,'和',word_li[k+i])
i += 1
fin = open('words.txt')
word_list = read_word1(fin)
findpairs(word_list)
|
我在10.10题写的in_bisect函数有误差，导致上面的代码虽然能找到‘‘反转词对’，但在输出的时候有偏差。今天很晚了(0:44)，后面有机会再改吧。
下面我用了Python的bisect模块：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| import bisect
def read_word1(file_in): #来自10.9
word_list = []
for line in file_in:
word = line.strip()
word_list.append(word)
return word_list
def findpairs(word_li):
for i in range(len(word_li)):
drow = word_li[i][::-1] #将单词里的字母按照相反的顺序排列
k = bisect.bisect(word_li[i:],drow) #写word_list[i:]目的是不让程序往前去找所谓的“反转词”
if drow == word_li[i+k-1]:
print(i,word_li[i],'和',i+k-1,word_li[i+k-1])
fin = open('words.txt')
word_list = read_word1(fin)
findpairs(word_list)
|
输出看起来很美好，但是我稍微变一下，它就不正常了：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| import bisect
def read_word1(file_in): #来自10.9
word_list = []
for line in file_in:
word = line.strip()
word_list.append(word)
return word_list
def findpairs(word_li):
for i in range(len(word_li)):
drow = word_li[i][::-1] #将单词里的字母按照相反的顺序排列
k = bisect.bisect(word_li[i:],drow) #写word_list[i:]目的是不让程序往前去找所谓的“反转词”
if k:
print(i,word_li[i],'和',i+k-1,word_li[i+k-1])
fin = open('words.txt')
word_list = read_word1(fin)
findpairs(word_list)
|
我把if里的drow == word_li[i+k-1]改成k，输出就不正常了，打印出来的一对单词 就不是‘‘反转词对’’了。而且因为单词表里的单词很多（十几万个），电脑还会卡死。
看看作者答案是怎么写的吧：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| from __future__ import print_function, division
from inlist import in_bisect, make_word_list
def reverse_pair(word_list, word):
rev_word = word[::-1]
return in_bisect(word_list, rev_word)
if __name__ == '__main__':
word_list = make_word_list()
for word in word_list:
if reverse_pair(word_list,word):
print(word, word[::-1])
|
有点失望，作者的代码完全没有涉及到下标的加加减减。