Незначительная оптимизация может быть выполнена путем перечисления возможностей перед выполнением возврата. В Python:
dictionary = ['and', 'dick', 'jane', 'puff', 'spot', 'yertle']
line = ['bjvg', 'xsb', 'hxsn', 'xsb', 'qymm', 'xsb', 'rqat', 'xsb', 'pnetfn']
# ------------------------------------
import collections
words_of_length = collections.defaultdict(list)
for word in dictionary:
words_of_length[len(word)].append(word)
possibilities = collections.defaultdict(set)
certainities = {}
for word in line:
length = len(word)
for i, letter in enumerate(word):
if len(words_of_length[length]) == 1:
match = words_of_length[length][0]
certainities[letter] = match[i]
else:
for match in words_of_length[length]:
possibilities[letter].add(match[i])
for letter in certainities.itervalues():
for k in possibilities:
possibilities[k].discard(letter)
for i, j in certainities.iteritems():
possibilities[i] = set([j])
# ------------------------------------
import pprint
pprint.pprint(dict(possibilities))
Выход:
{'a': set(['c', 'f', 'o']),
'b': set(['d']),
'e': set(['r']),
'f': set(['l']),
'g': set(['f', 'k']),
'h': set(['j', 'p', 's']),
'j': set(['i', 'p', 'u']),
'm': set(['c', 'f', 'k', 'o']),
'n': set(['e']),
'p': set(['y']),
'q': set(['i', 'j', 'p', 's', 'u']),
'r': set(['j', 'p', 's']),
's': set(['n']),
't': set(['t']),
'v': set(['c', 'f', 'o']),
'x': set(['a']),
'y': set(['i', 'p', 'u'])}
Если у вас есть несколько одноэлементных возможностей, вы можете исключить их из входных данных и повторно запустить алгоритм.
РЕДАКТИРОВАТЬ: Переключено на установку вместо списка и добавлен код печати.