Strykord

Tomt ord är stamfar, barnen får man genom att lägga på en bokstav och kolla i ordlistan. Eftersom man inte är ute efter kortaste strykord utan tvärtom längsta är breddenförst inte nödvändigt. Rekursiv djupetförst som går igenom hela trädet och noterar längdrekord är kanske bäst, särskilt eftersom letandet i ordlistan då hela tiden går framåt! Här har jag lagt alla svenska ord i ett binärträd - det tar förstås mycket minne och är onödigt. Man kan i stället läsa filen ord för ord eftersom man aldrig behöver backa.

def byggut(ord):
    """ Rekursiv djupetförst"""
    global rekord
    if len(ord) > len(rekord): 
       rekord = ord
    for tkn in alfabet:
      if svenska.exists(ord+tkn):
          byggut(ord+tkn)


from bintree import Bintree
alfabet="abcdefghijklmnopqrstuvwxyzåäö"
rekord=""

svenska=Bintree()
svenskfil = open("words.txt")
for rad in svenskfil.readlines():
    svenska.put(rad.strip())     #Ta bort returtecknet

byggut("")
print("Längsta strykord: ", rekord)

Lärare Linda Kann skapade sidan 13 september 2016

Feedback Nyheter