<p>您可以构建一个<code>dict</code>,将单词的根作为键,将列表中的所有变体作为值。那么我们只保留3个值的条目。这样,我们只在列表上迭代一次,在我们创建的dict上迭代一次,使整个过程保持O(n)。你知道吗</p>
<p>我们可以使用<code>defaultdict</code>更容易地构建dict。请注意<code>root</code>函数可能需要一些改进,请查看英语形容词列表!你知道吗</p>
<pre><code>from collections import defaultdict
def root(word):
if len(word) < 4:
return word
if word[-3:] == 'ier':
return word[:-3] + 'y'
elif word[-4:] == 'iest':
return word[:-4] + 'y'
elif word[-2:] == 'er':
return word[:-2]
elif word[-3:] == 'est':
return word[:-3]
else:
return word
def find_triples(words):
out_dict = defaultdict(list)
for word in words:
out_dict[root(word)].append(word)
# keep only the lists with 3 distinct values, sorted by length
out = [sorted(set(values), key=len) for values in out_dict.values()
if len(set(values))==3]
return out
data = ['early', 'earlier', 'earliest', 'or', 'hard', 'harder', 'hardest', 'ignored']
print(find_triples(data))
# [['early', 'earlier', 'earliest'], ['hard', 'harder', 'hardest']]
</code></pre>