我有一个问题，需要实现一个具有不同逻辑的单词阶梯问题。
在每一步中，玩家必须在前一步的单词上添加一个字母，或者删除一个字母，然后重新排列字母以形成一个新单词。
croissant(-C) -> arsonist(-S) -> aroints(+E)->notaries(+B)->baritones(-S)->baritone
新单词应该在单词列表wordList.txt中，该列表是一个单词字典。
我的代码看起来像这样，我首先计算了移除的字符数”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 = 0for 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_stringprint final_listflag_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 = 1sorted_removed_string = sorted_joined_string回答：
基于递归的回溯对于此类搜索问题来说不是一个好主意。它盲目地向下搜索树进行搜索，没有利用到单词之间几乎从不相距10-12个距离的事实，导致堆栈溢出（或Python中的递归限制超出）。
这里的解决方案使用广度优先搜索。它使用mate(s)作为辅助函数，给定一个单词s，找到我们可以前往的所有可能的单词。mate反过来使用一个全局字典wdict，在程序开始时预处理，对于给定的单词，找到它的所有字谜（即字母的重新排列）。
from queue import Queuewords = 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] = curprint(bfs('croissant','baritone'))输出为： ['croissant', 'arsonist', 'rations', 'senorita', 'baritones', 'baritone']
