没有替换的字梯在python中

Question

我有疑问，我需要用不同的逻辑来实现梯形图问题。

在每个步骤中，玩家必须在上一步中为单词添加一个字母，或者删掉一个字母，然后重新排列这些字母以创建一个新单词。

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

新单词应该从wordList.txt有意义，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']