python 中没有替换的字梯

Question

我有问题，我需要在哪里实现不同逻辑的梯形图问题。

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

羊角面包(-C) -> 纵火犯(-S) -> 公证人(+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 距离的事实，导致 Whosebug（或在 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']

python 中没有替换的字梯

Word Ladder without replacement in python

python

python-3.x

recursion

artificial-intelligence

breadth-first-search