Den längsten Teilstring in alphabetischer Reihenfolge finden

EDIT : Ich bin mir bewusst, dass eine Frage mit ähnlicher Aufgabe bereits in SO gefragt wurde, aber ich bin interessiert, das Problem in diesem spezifischen Code zu finden. Ich bin mir auch bewusst, dass dieses Problem ohne Rekursion gelöst werden kann.

Die Aufgabe besteht darin, ein Programm zu schreiben, das den längsten Unterstring findet, in dem die Buchstaben in alphabetischer Reihenfolge auftreten. Wenn mehr als 1 gleich lange Sequenzen gefunden wurden, dann sollte die erste gedruckt werden. Zum Beispiel wird die Ausgabe für einen String abczabcd abcz .

Ich habe dieses Problem mit der Rekursion gelöst, die meine manuellen Tests zu übergeben schien. Allerdings, wenn ich eine automatisierte Tests Set, die zufällige Zeichenfolgen zu generieren, habe ich bemerkt, dass in einigen Fällen die Ausgabe ist falsch. Beispielsweise:

Wenn s = 'hixwluvyhzzzdgd' , ist die Ausgabe hix statt luvy

Wenn s = 'eseoojlsuai' , ist die Ausgabe eoo statt jlsu

Wenn s = 'drurotsxjehlwfwgygygxz' , ist die Ausgabe dru statt ehlw

Nach einiger Zeit kämpfen, konnte ich nicht herausfinden, was ist so besonders an diesen Saiten, die den Bug verursacht.

Das ist mein Code:

 pos = 0 maxLen = 0 startPos = 0 endPos = 0 def last_pos(pos): if pos < (len(s) - 1): if s[pos + 1] >= s[pos]: pos += 1 if pos == len(s)-1: return len(s) else: return last_pos(pos) return pos for i in range(len(s)): if last_pos(i+1) != None: diff = last_pos(i) - i if diff - 1 > maxLen: maxLen = diff startPos = i endPos = startPos + diff print s[startPos:endPos+1] 

14 Solutions collect form web for “Den längsten Teilstring in alphabetischer Reihenfolge finden”

Es gibt viele Dinge, um in Ihrem Code zu verbessern, aber machen minimale Änderungen, um es zu funktionieren. Das Problem solltest du haben, if last_pos(i) != None: in deiner for Schleife ( i statt i+1 ) und du solltest diff (nicht diff - 1 ) gegen maxLen . Bitte lesen Sie andere Antworten, um zu lernen, wie es besser geht.

 for i in range(len(s)): if last_pos(i) != None: diff = last_pos(i) - i + 1 if diff > maxLen: maxLen = diff startPos = i endPos = startPos + diff - 1 

Hier. Das tut was du willst Ein Durchgang, keine Notwendigkeit für Rekursion.

 def find_longest_substring_in_alphabetical_order(s): groups = [] cur_longest = '' prev_char = '' for c in s.lower(): if prev_char and c < prev_char: groups.append(cur_longest) cur_longest = c else: cur_longest += c prev_char = c return max(groups, key=len) if groups else s 

Es benutzen:

 >>> find_longest_substring_in_alphabetical_order('hixwluvyhzzzdgd') 'luvy' >>> find_longest_substring_in_alphabetical_order('eseoojlsuai') 'jlsu' >>> find_longest_substring_in_alphabetical_order('drurotsxjehlwfwgygygxz') 'ehlw' 

Anmerkung: Es wird wahrscheinlich auf seltsame Zeichen brechen, wurde nur mit den Eingaben getestet, die du vorgeschlagen hast. Da dies eine "Hausaufgaben" Frage ist, werde ich Sie mit der Lösung verlassen, wie es ist, obwohl es noch eine Optimierung zu tun gibt, wollte ich es ein bisschen verständlich lassen.

Sie können verschachtelt for Loops, Slicing und sorted . Wenn die Zeichenfolge nicht alle Kleinbuchstaben ist, können Sie die Unterstrings in Kleinbuchstaben umwandeln, bevor sie mit str.lower verglichen werden:

 def solve(strs): maxx = '' for i in xrange(len(strs)): for j in xrange(i+1, len(strs)): s = strs[i:j+1] if ''.join(sorted(s)) == s: maxx = max(maxx, s, key=len) else: break return maxx 

Ausgabe:

 >>> solve('hixwluvyhzzzdgd') 'luvy' >>> solve('eseoojlsuai') 'jlsu' >>> solve('drurotsxjehlwfwgygygxz') 'ehlw' 

Hier ist eine Single-Pass-Lösung mit einer schnellen Schleife. Es liest jeden Charakter nur einmal. Innerhalb der Schleifenoperationen sind begrenzt auf

  • 1 String Vergleich (1 char x 1 char)
  • 1 Integer-Inkrement
  • 2 Integer-Subtraktionen
  • 1 Integer Vergleich
  • 1 bis 3 Integer-Zuweisungen
  • 1 String Zuordnung

Es werden keine Behälter verwendet. Es werden keine Funktionsaufrufe gemacht. Der leere String wird ohne Sondercode abgelegt. Alle Zeichencodes, einschließlich chr (0), werden ordnungsgemäß behandelt. Wenn es eine Bindung für den längsten alphabetischen Teilstring gibt, gibt die Funktion den ersten gewinnenden Teilstring zurück, den es angetroffen hat. Fall wird für die Alphabetisierung ignoriert, aber der Fall wird im Ausgabe-Teilstring beibehalten.

 def longest_alphabetical_substring(string): start, end = 0, 0 # range of current alphabetical string START, END = 0, 0 # range of longest alphabetical string yet found prev = chr(0) # previous character for char in string.lower(): # scan string ignoring case if char < prev: # is character out of alphabetical order? start = end # if so, start a new substring end += 1 # either way, increment substring length if end - start > END - START: # found new longest? START, END = start, end # if so, update longest prev = char # remember previous character return string[START : END] # return longest alphabetical substring 

Ergebnis

 >>> longest_alphabetical_substring('drurotsxjehlwfwgygygxz') 'ehlw' >>> longest_alphabetical_substring('eseoojlsuai') 'jlsu' >>> longest_alphabetical_substring('hixwluvyhzzzdgd') 'luvy' >>> 

Python hat ein leistungsfähiges eingebautes Paket itertools und eine wundervolle Funktion innerhalb groupby

Eine intuitive Nutzung der Key-Funktion kann immense Meilenzahl geben.

In diesem speziellen Fall müssen Sie nur eine Reihenfolge der Reihenfolge ändern und gruppieren Sie die Reihenfolge entsprechend. Die einzige Ausnahme ist der Grenzfall, den man separat behandeln muss

Code

 def find_long_cons_sub(s): class Key(object): ''' The Key function returns 1: For Increasing Sequence 0: For Decreasing Sequence ''' def __init__(self): self.last_char = None def __call__(self, char): resp = True if self.last_char: resp = self.last_char < char self.last_char = char return resp def find_substring(groups): ''' The Boundary Case is when an increasing sequence starts just after the Decresing Sequence. This causes the first character to be in the previous group. If you do not want to handle the Boundary Case seperately, you have to mak the Key function a bit complicated to flag the start of increasing sequence''' yield next(groups) try: while True: yield next(groups)[-1:] + next(groups) except StopIteration: pass groups = (list(g) for k, g in groupby(s, key = Key()) if k) #Just determine the maximum sequence based on length return ''.join(max(find_substring(groups), key = len)) 

Ergebnis

 >>> find_long_cons_sub('drurotsxjehlwfwgygygxz') 'ehlw' >>> find_long_cons_sub('eseoojlsuai') 'jlsu' >>> find_long_cons_sub('hixwluvyhzzzdgd') 'luvy' 

Viel mehr Looping, aber es wird die Arbeit erledigt

 s = raw_input("Enter string") fin="" s_pos =0 while s_pos < len(s): n=1 lng=" " for c in s[s_pos:]: if c >= lng[n-1]: lng+=c n+=1 else : break if len(lng) > len(fin): fin= lng`enter code here` s_pos+=1 print "Longest string: " + fin 
 def find_longest_order(): `enter code here`arr = [] `enter code here`now_long = '' prev_char = '' for char in s.lower(): if prev_char and char < prev_char: arr.append(now_long) now_long = char else: now_long += char prev_char = char if len(now_long) == len(s): return now_long else: return max(arr, key=len) def main(): print 'Longest substring in alphabetical order is: ' + find_longest_order() main() 

Einfach und einfach.

Code:

 s = 'hixwluvyhzzzdgd' r,p,t = '','','' for c in s: if p <= c: t += c p = c else: if len(t) > len(r): r = t t,p = c,c if len(t) > len(r): r = t print 'Longest substring in alphabetical order is: ' + r 

Ausgabe :

 Longest substring in alphabetical order which appeared first: luvy 

Einfach und leicht zu verstehen:

 s = "abcbcd" #The original string l = len(s) #The length of the original string maxlenstr = s[0] #maximum length sub-string, taking the first letter of original string as value. curlenstr = s[0] #current length sub-string, taking the first letter of original string as value. for i in range(1,l): #in range, the l is not counted. if s[i] >= s[i-1]: #If current letter is greater or equal to previous letter, curlenstr += s[i] #add the current letter to current length sub-string else: curlenstr = s[i] #otherwise, take the current letter as current length sub-string if len(curlenstr) > len(maxlenstr): #if current cub-string's length is greater than max one, maxlenstr = curlenstr; #take current one as max one. print("Longest substring in alphabetical order is:", maxlenstr) 
 s = input("insert some string: ") start = 0 end = 0 temp = "" while end+1 <len(s): while end+1 <len(s) and s[end+1] >= s[end]: end += 1 if len(s[start:end+1]) > len(temp): temp = s[start:end+1] end +=1 start = end print("longest ordered part is: "+temp) 

Ich nehme an, das ist Problem gesetzt Frage für CS6.00.1x auf EDX. Hier ist, was ich kam mit.

 s = raw_input("Enter the string: ") longest_sub = "" last_longest = "" for i in range(len(s)): if len(last_longest) > 0: if last_longest[-1] <= s[i]: last_longest += s[i] else: last_longest = s[i] else: last_longest = s[i] if len(last_longest) > len(longest_sub): longest_sub = last_longest print(longest_sub) 

Ich kam mit dieser Lösung auf

 def longest_sorted_string(s): max_string = '' for i in range(len(s)): for j in range(i+1, len(s)+1): string = s[i:j] arr = list(string) if sorted(string) == arr and len(max_string) < len(string): max_string = string return max_string 
 s = 'gkuencgybsbezzilbfg' x = s.lower() y = '' z = [] #creating an empty listing which will get filled for i in range(0,len(x)): if i == len(x)-1: y = y + str(x[i]) z.append(y) break a = x[i] <= x[i+1] if a == True: y = y + str(x[i]) else: y = y + str(x[i]) z.append(y) # fill the list y = '' # search of 1st longest string L = len(max(z,key=len)) # key=len takes length in consideration for i in range(0,len(z)): a = len(z[i]) if a == L: print 'Longest substring in alphabetical order is:' + str(z[i]) break 
 first_seq=s[0] break_seq=s[0] current = s[0] for i in range(0,len(s)-1): if s[i]<=s[i+1]: first_seq = first_seq + s[i+1] if len(first_seq) > len(current): current = first_seq else: first_seq = s[i+1] break_seq = first_seq print("Longest substring in alphabetical order is: ", current) 
  • Merkwürdiges Rekursionsverhalten in Python
  • Python: Rekursive Funktion, um die größte Zahl in der Liste zu finden
  • Python-interpretator automatisch wiederherzustellen, ohne Antwort zurückzugeben
  • Rekursive Funktion gibt keine in Python zurück [doppelte]
  • Python RuntimeError: maximale Rekursionstiefe überschritten
  • Finde alle Index mit Rekursion
  • Python-Rekursions-Permutationen
  • Python rekursive Funktion, die von 0 bis n?
  • Berechnungsdeterminante einer Matrix (nxn) rekursiv
  • Baktracking-Funktion, die die Berechnung berechnet, überschreitet die maximale Rekursionstiefe
  • Rekursiv finden Sie alle Münzkombinationen, die eine bestimmte Menge produzieren
  • Python ist die beste Programmiersprache der Welt.