4

我有一个单词列表，例如：

l = """abc
dfg
hij
jih
gfd
cba
cbd
jip
gfe
jiw
cbw"""

我想从这个列表中找到成对的单词，所以第一个单词是：

.(.)(.)

第二个词是：

\2\1.

所以 \1 和 \2 指的是第一个单词中的字符。

我能想到的最好的正则表达式是：

re.findall('(^.(?P<A>.)(?P<B>.)$)(?=.*(^(?P=B)(?P=A).$))', l, re.DOTALL | re.MULTILINE)

但是这个搜索只返回一些对（因为 findall 只返回不重叠的结果......）。然后我想到了使用肯定的lookbehind断言，但它们只能与固定长度的字符串一起使用......

有没有办法用正则表达式做到这一点？

4

1 回答 1

2

我怀疑正则表达式是做到这一点的好方法（特别是在 Python 中，你不能像 Perl 那样简单地获得匹配字符串的所有可能方法，所以你必须调用findall字符串的所有前缀）。一个直接的替代方案是：

words = l.split()
pairs = set(frozenset((w1, w2)) for w1 in words for w2 in words 
                      if w1[1:] == w2[1::-1])

结果是：

>>> map(tuple, pairs)
[('hij', 'jip'), 
 ('abc', 'cbd'), 
 ('dfg', 'gfd'), 
 ('dfg', 'gfe'), 
 ('jiw', 'hij'), 
 ('hij', 'jih'), 
 ('abc', 'cbw'), 
 ('abc', 'cba')]

您还可以通过在第一遍中将单词的前缀保存在字典中，然后在第二遍中建立关联来快速解决这个问题：

from collections import defaultdict

prefixes = defaultdict(list)
for w in words:
    prefixes[w[1::-1]].append(w) 
pairs = set(frozenset((w1, w2)) for w1 in words for w2 in prefixes[w1[1:]])

正则表达式引擎很难超越它的性能。

于 2012-05-01T19:09:42.340 回答