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) |