String-Parsing mit Python?

Question

Gegeben eine Zeichenfolge wie "helloyellowellow", analysieren Sie alle gültigen Zeichenfolgen aus der angegebenen Zeichenfolge. (ZB: [[hell, hallo, gelb], [low, low] .........]]

Ich bin auf der Suche nach der optimierten Art den Code zu schreiben, hier ist meins, aber ich bin es nicht sicher, ob dies der beste Weg ist

vollständige Offenlegung - das war eine Interviewfrage

master = [] 

# Dictionary for us to look up words 
def is_word(inputstr): 
    #returns True/False 


def processstring(fstr,secstr,li): 
    if is_word(fstr): 
     li.append(fstr) 
    if len(secstr) == 0: 
     if len(li) != 0: 
      master.append(li) 
     return 
    processstring(fstr+secstr[0], secstr[1:len(secstr)],li) 



def wrapperprocess(inpstr): 
    li = [] 
    if len(inpstr) == 0: 
     return 
    processstring('',inpstr,li) 
    wrapperprocess(inpstr[1:len(inpstr)]) 


wrapperprocess('helloyellowellow') 
print master 

Answer 1

Sie so etwas wie tun könnte.

tgt='helloyellowellow' 

with open('/usr/share/dict/words') as f: 
    for word in f: 
     word=word.strip() 
     if word in tgt and len(word)>1: 
      print word 

Drucke:

Wenn Sie suchen, nur für die Funktion is_word, die Sie nicht definiert haben, können Sie mit so etwas wie dieses spielen:

def is_word(word, dic='/usr/share/dict/words'): 
    if not hasattr(is_word, 'words'): 
     with open(dic) as f: 
      is_word.words={word.strip() for word in f} 

    return word in is_word.words and len(word)>1 

Als Standarddatenstruktur, Python-Sets haben eine durchschnittliche look-up time of O(1). Es ist sehr unwahrscheinlich, dass Sie selbst etwas schreiben, das schneller ist.

Answer 2

Es ist gut, Problem,

Verwenden Wordnet Paket,

zu lösen Während Ihre Strings mit einem gewissen Index beginnen Parsen und halten Sie Ihren Indexwert für jede inkrementelle auf dem Index quälende, überprüfen Sie die Existenz das gleiche wort mit wordnet, es wird dir sagen, wetter die bestimmte sub-string ist eine bedeutung oder nicht!

installieren wordnet:

https://pypi.python.org/pypi/Wordnet-bn/1.0 

Answer 3

Da Sie erwähnt Sie für einen effizienten Algorithmus sucht, und vorausgesetzt, Sie das Wörterbuch im Voraus erhalten (und nicht nur als aufrufbare Prädikat), können Sie die Aho–Corasick verwenden Algorithmus.

Natürlich, wenn der Eingabetext kurz ist, wird ein naive Algorithmus schneller sein, um die "teure" Vorverarbeitung des Wörterbuchs zu vermeiden.

Plus eine alternative Python-Antwort: hier ist ein einfacher Weg, um einfach jede Teilkette zu überprüfen:

def gen_words(txt): 
    n = len(txt) 
    for i in range(n): 
     for j in range(i+1, n+1): 
      subtxt = txt[i:j] 
      if is_word(subtxt): 
       yield subtxt 

Für Einzigartigkeit tun:

all_words = set(gen_words(txt))