我正在尝试在python中实现以下“游戏”：
给定一个起始单词，找到目标单词，并对其进行允许的修改（可对每个步骤进行修改）：删除或添加任何字母并进行置换
任务是以最少的步骤找到从开始到实现目标的方法。
我的方法是添加/删除字母，置换生成的字母，并查找字典中的每个置换。
这很快导致运行时间长（对于一个9字母的单词，第一步大约需要60秒）。
这是我的代码。
import time
from itertools import permutations
startword = 'croissant'
nodes = list()
nodes.append(startword)
dicts = set([line.rstrip('\n') for line in open('wordList.txt')])
alpha = set([chr(i) for i in range(ord('a'),ord('z')+1)])
def step(nodes):
nnodes = list()
for word in nodes:
for s in word:
new_word = word.replace(s, '', 1)
perms = [''.join(p) for p in permutations(new_word)]
for per in perms:
if per in dicts:
nnodes.append(per)
for s in alpha:
new_word = word + s
perms = [''.join(p) for p in permutations(new_word)]
for per in perms:
if per in dicts:
nnodes.append(per)
return set(nnodes)
btime = time.time()
step(nodes)
print time.time() - btime
如何改善性能/逻辑？特别要求我们使用广度优先搜索。
有趣的问题！有一种方法可以极大地提高性能。可以通过遍历单词列表并检查是否存在每个单词来检查每个新单词，而无需按字母顺序将单词列表中每个单词的字符按字母顺序排列，然后直接将它们与按字母顺序排列的缩短/加长的关注单词进行比较。
例如，使用croissant，我可以按字母顺序生成字符acinorsst。然后，我检查是否acinorsst默认情况下删除或添加了一个字符是否在列表的默认值中，其中键是按字母顺序排列的字符串，并检索相应的值（这是与该字母顺序相对应的实际单词的列表）。
用代码解释的过程要少得多，所以我在下面发布了它：
from collections import defaultdict
import itertools as its
import time
def get_alpha_dicts():
wa_dict = {}#word: alphabetized dict
aw_dict = defaultdict(list)#alphabetized: corresponding WORDS dict
for line in open('wordList.txt'):
word = line.rstrip('\n')
alpha_word = ''.join(sorted(word))
wa_dict[word] = alpha_word
aw_dict[alpha_word].append(word)
return wa_dict, aw_dict
def step(nodes, aw_dict):
alpha = set([chr(i) for i in range(ord('a'),ord('z')+1)])
nnodes = list()
for word in nodes:
alpha_word = ''.join(sorted(word))
#remove a char from word
short_words = set([''.join(w) for w in its.combinations(alpha_word, len(start_word)-1)])
for short_word in short_words:
nnodes.extend(aw_dict[short_word])
#add a char to word
long_words = [''.join(sorted(alpha_word + s)) for s in alpha]
for long_word in long_words:
nnodes.extend(aw_dict[long_word])
return set(nnodes)
if __name__ == "__main__":
start_word = 'croissant'
nodes = list()
nodes.append(start_word)
wa_dict, aw_dict = get_alpha_dicts()
btime = time.time()
print step(nodes, aw_dict)
print time.time() - btime
希望能帮助到你！
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句