python - python中无替换的Word Ladder

Question

我有问题，我需要在哪里用不同的逻辑来实现梯子问题。

在每一步中，玩家必须向单词添加一个字母从上一步中删除一个字母，然后重新排列字母以组成一个新单词。

羊角面包(-C) -> 纵火犯(-S) -> aroints(+E)->公证人(+B)->男中音(-S)->男中音

新单词应该从单词字典 wordList.txt 中理解。

Dictionary

我的代码看起来像这样，我首先计算了删除“remove_list”并添加“add_list”的字符数。然后我将该值存储在列表中。

然后我读取该文件，并将已排序的对存储到字典中。

然后我开始删除并添加到起始词中并与字典匹配。

但现在的挑战是，删除和添加后的某些单词与词典不匹配，达不到目标。

在这种情况下，它应该回溯到上一步并且应该加而不是减。

我正在寻找某种递归函数，它可以帮助完成这个或完成新的逻辑，我可以帮助实现输出。

我的代码示例。

start = 'croissant'
goal =  'baritone'

list_start = map(list,start)
list_goal = map(list, goal)



remove_list = [x for x in list_start if x not in list_goal]

add_list = [x for x in list_goal if x not in list_start]



file = open('wordList.txt','r')
dict_words = {}
for word in file:
   strip_word = word.rstrip()
   dict_words[''.join(sorted(strip_word))]=strip_word
   file.close()
final_list = []


flag_remove = 0

for i in remove_list:
   sorted_removed_list = sorted(start.replace(''.join(map(str, i)),"",1))
   sorted_removed_string = ''.join(map(str, sorted_removed_list))

   if sorted_removed_string in dict_words.keys():
       print dict_words[sorted_removed_string]
       final_list.append(sorted_removed_string)
       flag_remove = 1
   start = sorted_removed_string
print final_list


flag_add = 0    
for i in add_list:
    first_character = ''.join(map(str,i))
    sorted_joined_list = sorted(''.join([first_character, final_list[-1]]))
    sorted_joined_string = ''.join(map(str, sorted_joined_list))

   if sorted_joined_string in dict_words.keys():
       print dict_words[sorted_joined_string]
       final_list.append(sorted_joined_string)
       flag_add = 1
sorted_removed_string = sorted_joined_string

Answer 1

对于此类搜索问题，基于递归的回溯并不是一个好主意。它盲目地在搜索树中向下搜索，没有利用单词之间几乎没有 10-12 距离的事实，从而导致 StackOverflow(或在 Python 中超出递归限制)。

这里的解决方案使用广度优先搜索。它使用 mate(s) 作为助手，给定一个单词 s，找到我们接下来可以移动到的所有可能的单词。 mate 反过来使用全局字典 wdict，在程序开始时进行预处理，对于给定的单词，找到它的所有字谜词(即字母的重新排列) )。

from queue import Queue
words = set(''.join(s[:-1]) for s in open("wordsEn.txt"))
wdict = {}
for w in words:
    s = ''.join(sorted(w))
    if s in wdict: wdict[s].append(w)
    else: wdict[s] = [w]

def mate(s):
    global wdict
    ans = [''.join(s[:c]+s[c+1:]) for c in range(len(s))]
    for c in range(97,123): ans.append(s + chr(c))
    for m in ans: yield from wdict.get(''.join(sorted(m)),[])

def bfs(start,goal,depth=0):
    already = set([start])
    prev = {}
    q = Queue()
    q.put(start)
    while not q.empty():
        cur = q.get()
        if cur==goal:
            ans = []
            while cur: ans.append(cur);cur = prev.get(cur)
            return ans[::-1] #reverse the array
        for m in mate(cur):
            if m not in already:
                already.add(m)
                q.put(m)
                prev[m] = cur


print(bfs('croissant','baritone'))

输出:['croissant', 'arsonist', 'rations', 'senorita', 'baritones', 'baritone']