Wie vermeidet man Laufzeitfehler bei dieser Kodierung?

Question

Ich schließe this HackerRank Codierung Herausforderung. Im Wesentlichen fordert uns die Herausforderung auf, alle Teilzeichenfolgen der Eingabezeichenfolge zu finden, ohne die Buchstaben zu mischen. Dann zählen wir die Anzahl der Teilstrings, die mit einem Vokal beginnen und zählen die Anzahl der Teilstrings, die mit einem Konsonanten beginnen.

Die Codierung Herausforderung ist als ein Spiel strukturiert, wo Stuart die Anzahl der Konsonanten beginnt Teilstrings und Kevins Punktzahl ist die Anzahl der Vokal beginnt Teilstrings. Das Programm gibt den Gewinner aus, d. H. Den mit den meisten Teilstrings.

Zum Beispiel habe ich den folgenden Code:

def constwordfinder(word): 
    word = word.lower() 
    return_lst = [] 
    for indx in range(1,len(word)+1): 
     if word[indx-1:indx] not in ['a','e','i','o','u']: 
      itr = indx 
      while itr < len(word)+1: 
       return_lst.append(word[indx-1:itr]) 
       itr +=1 
    return return_lst 

def vowelwordfinder(word): 
    word = word.lower() 
    return_lst = [] 
    for indx in range(1,len(word)+1): 
     if word[indx-1:indx] in ['a','e','i','o','u']: 
      itr = indx 
      while itr < len(word)+1: 
       return_lst.append(word[indx-1:itr]) 
       itr +=1 
    return return_lst 

def game_scorer(const_list, vow_list): 
    if len(const_list) == len(vow_list): 
     return 'Draw' 
    else: 
     if len(const_list) > len(vow_list): 
      return 'Stuart ' + str(len(const_list)) 
     else: 
      return 'Kevin ' + str(len(vow_list)) 

input_str = input() 
print(game_scorer(constwordfinder(input_str), vowelwordfinder(input_str))) 

Diese für kleinere Strings wie BANANA gearbeitet, obwohl, wenn HackerRank Eingabe von Zeichenketten wie die folgenden begann, habe ich mehrere Laufzeitfehler auf den Testfällen bekam:

NANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANANNANAN 

ich habe versucht, das Programm zu strukturieren etwas knapper zu sein, obwohl ich nach wie vor Laufzeitfehler auf den längeren Testfällen bekam:

def wordfinder(word): 
    word = word.lower() 
    return_lst = [] 
    for indx in range(1,len(word)+1): 
     itr = indx 
     while itr < len(word)+1: 
      return_lst.append(word[indx-1:itr]) 
      itr +=1 
    return return_lst 

def game_scorer2(word_list): 
    kevin_score = 0 
    stuart_score = 0 
    for word in word_list: 
     if word[0:1] not in ['a','e','i','o','u']: 
      stuart_score += 1 
     else: 
      kevin_score +=1 
    if stuart_score == kevin_score: 
     return 'Draw' 
    else: 
     if stuart_score > kevin_score: 
      return 'Stuart ' + str(stuart_score) 
     else: 
      return 'Kevin ' + str(kevin_score) 

print(game_scorer2(wordfinder(input()))) 

Was sollte ich noch tun, um mein Programm zu strukturieren, um Laufzeitfehler wie zuvor zu vermeiden?

Answer 1

Das Problem hier ist Ihr Algorithmus. Sie finden alle Unterzeichenfolgen des Textes. Es braucht exponentielle Zeit, um das Problem zu lösen. Deshalb haben Sie hier Laufzeitfehler bekommen. Sie müssen einen anderen guten Algorithmus verwenden, um dieses Problem zu lösen, anstatt Sub-Strings zu verwenden.

Answer 2

Hier ist eine schnelle und schmutzige Teillösung basierend auf meine Hinweise:

input_str = raw_input() 
kevin = 0 
for i, c in enumerate(input_str): 
    if c.lower() in "aeiou": 
     kevin += len(input_str) - i 
print kevin 

Grundsätzlich über jedes Zeichen durchlaufen, und wenn es in dem Satz von Vokalen, Kevins Punktzahl erhöht sich die Anzahl der verbleibenden Zeichen in die Saite.

Die verbleibende Arbeit sollte ziemlich offensichtlich sein, hoffe ich!

[aus dem Bereich der Website in Frage Spoiler gestohlen]

Denn für sagen jeder Konsonant, können Sie n Teil mit diesem consanant Anfang machen. So für die BANANA Beispiel Blick auf die erste B. Mit dieser B können Sie machen: B, BA, BAN, BANA, BANAN, BANANA. Das sind sechs Teilstrings, beginnend mit dem B oder , was bedeutet, dass B6 zu der Punktzahl hinzufügt. Also gehst du durch die Saite, suchst nach jedem Konsonanten und fügst length(string) - index zur Partitur hinzu.