ฉันมีรายการคำยาวสามตัวอักษร 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)
