У меня есть список из 794 длинных слов из трех букв. Моя задача — найти слово (слова) с самым длинным путем к заданному слову.
Определение (дочерние элементы).
Дочерними элементами родительского слова являются родительские слова с заменой одной и только одной буквы.
Пример:
"can", "run", "rap" и т. д. являются дочерними элементами слова "ran" (учитывая, что эти слова существуют в списке).
Определение (путь):
Путь — это последовательность слов, в которой каждое слово создается путем замены одной буквы в предыдущем.
#Pseudo code
Given a word
Put the word in a queue
Keep a list with all visited words
As long as the queue is not empty
Get the first word in the queue
Generate a list with all the children to this word
For every children in that list
If the child is not in the list of visited words
Append the child to the list of visited words
Put the child in the queue
Print the path to the last grandchild.
Моя идея состоит в том, что это даст самый длинный путь, поскольку мы продолжаем генерировать новые дочерние элементы, пока у нас не закончатся возможные дочерние элементы (то есть дочерние элементы, которые еще не были посещены).
Вопрос.
Верна ли моя идея? Как я могу проверить, действительно ли это работает?
Фактический код можно посмотреть ниже, но без комментариев он может быть бессмысленным.
Редактировать
Поскольку деревья и списки могут быть немного медленными, я заменил их наборами.
from Queue import Queuenode; import Bintree
with open('word3',encoding='utf-8') as f:
lista=f.readlines()
lista=[x.strip('\n') for x in lista]
alfabet='abcdefghijklmnopqrstuvwxyzåäö'
class Word:
def __init__(self, w, f = None):
self.word = w
self.parent = f
children=Bintree.Bintree()
for i in lista:
children.put(i)
def barn(far):
barnlista=[]
for i in range(3):
for j in range(29):
empty=''
empty+=far[0:i]+alfabet[j]+far[i+1:]
if empty!=far and children._exists(empty):
barnlista+=[empty]
return barnlista
ko=Queuenode()
def vag(item):
start=item
counter=0
while start!=None:
counter+=1
print(start.word)
start=start.parent
print(counter)
def bfsx(startord):
ko.put(Word(startord))
besokta=[startord]
while not ko.isempty():
first=ko.get()
lista=barn(first.word)
for child in lista:
if child not in besokta:
besokta+=[child]
ko.put(Word(child,first))
vag(first)
