Encontrar la subcadena más larga en orden alfabético

EDITAR : Soy consciente de que una pregunta con una tarea similar ya se hizo en SO, pero me interesa averiguar el problema en este código específico. También soy consciente de que este problema se puede resolver sin usar recursión.

La tarea es escribir un progtwig que encuentre (e imprima) la subcadena más larga en la que aparecen las letras en orden alfabético. Si se encuentran más de 1 secuencias igualmente largas, entonces se debe imprimir la primera. Por ejemplo, la salida para una cadena abczabcd será abcz .

Resolví este problema con la recursión que parecía pasar mis pruebas manuales. Sin embargo, cuando ejecuto un conjunto de pruebas automatizadas que generan cadenas aleatorias, he notado que en algunos casos, la salida es incorrecta. Por ejemplo:

si s = 'hixwluvyhzzzdgd' , la salida es hix lugar de luvy

si s = 'eseoojlsuai' , la salida es eoo lugar de jlsu

si s = 'drurotsxjehlwfwgygygxz' , la salida es dru lugar de ehlw

Después de un tiempo de lucha, no pude descubrir qué tienen de especial estas cadenas que causan el error.

Este es mi código:

 pos = 0 maxLen = 0 startPos = 0 endPos = 0 def last_pos(pos): if pos = 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] 

Hay muchas cosas que mejorar en su código, pero hacer cambios mínimos para que funcione. El problema es que debes tener if last_pos(i) != None: en tu bucle for ( i lugar de i+1 ) y debes comparar diff (no diff - 1 ) con maxLen . Por favor lea otras respuestas para aprender cómo hacerlo mejor.

 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 

Aquí. Esto hace lo que quieras. Una pasada, no hay necesidad de recursión.

 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 

Usándolo:

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

Nota: probablemente se romperá con caracteres extraños, solo se ha probado con las entradas que sugirió. Ya que esta es una pregunta de "tarea", los dejaré con la solución tal como está, aunque todavía hay algo de optimización por hacer, quería dejarla un poco comprensible.

Puedes usar nesteds for bucles, rebanar y sorted . Si la cadena no está en minúsculas, puede convertir las str.lower minúsculas antes de comparar con str.lower :

 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 

Salida:

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

Simple y fácil.

Código:

 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 

Salida:

 Longest substring in alphabetical order which appeared first: luvy 

Aquí hay una solución de un solo paso con un bucle rápido. Lee cada personaje solo una vez. Dentro de las operaciones de bucle se limitan a

  • 1 cadena de comparación (1 char x 1 char)
  • 1 incremento entero
  • 2 restas de enteros
  • 1 comparación de enteros
  • 1 a 3 asignaciones de enteros
  • Asignación de 1 cadena

No se utilizan contenedores. No se realizan llamadas a funciones. La cadena vacía se maneja sin un código de caso especial. Todos los códigos de caracteres, incluido chr (0), se manejan adecuadamente. Si hay un empate para la subcadena alfabética más larga, la función devuelve la primera subcadena ganadora que encontró. El caso se ignora para fines de alfabetización, pero el caso se conserva en la subcadena de salida.

 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 

Resultado

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

Python tiene un potente paquete integrado de herramientas y una función maravillosa dentro de groupby

Un uso intuitivo de la función de la tecla puede dar un kilometraje inmenso.

En este caso particular, solo tiene que hacer un seguimiento del cambio de orden y agrupar la secuencia en consecuencia. La única excepción es el caso límite que debe manejar por separado.

Código

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

Resultado

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

Mucho más bucles, pero hace el trabajo

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

Simple y fácil de entender:

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

Supongo que esta es una pregunta de conjunto de problemas para CS6.00.1x en EDX. Aquí es lo que se me ocurrió.

 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) 

Se me ocurrió esta solución

 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 

Asumiendo que esto es del curso Edx: hasta esta pregunta, no hemos enseñado nada acerca de las cadenas y sus operaciones avanzadas en python. Entonces, simplemente repasaría el bucle y las declaraciones condicionales.

 string ="" #taking a plain string to represent the then generated string present ="" #the present/current longest string for i in range(len(s)): #not len(s)-1 because that totally skips last value j = i+1 if j>= len(s): j=i #using s[i+1] simply throws an error of not having index if s[i] <= s[j]: #comparing the now and next value string += s[i] #concatinating string if above condition is satisied elif len(string) != 0 and s[i] > s[j]: #don't want to lose the last value string += s[i] #now since s[i] > s[j] #last one will be printed if len(string) > len(present): #1 > 0 so from there we get to store many values present = string #swapping to largest string string = "" if len(string) > len(present): #to swap from if statement present = string if present == s[len(s)-1]: #if no alphabet is in order then first one is to be the output present = s[0] print('Longest substring in alphabetical order is:' + present) 

Estoy de acuerdo con @Abhijit sobre el poder de itertools.groupby() pero itertools.groupby() un enfoque más simple para (ab) usarlo y evité los problemas de casos de límites:

 from itertools import groupby LENGTH, LETTERS = 0, 1 def longest_sorted(string): longest_length, longest_letters = 0, [] key, previous_letter = 0, chr(0) def keyfunc(letter): nonlocal key, previous_letter if letter < previous_letter: key += 1 previous_letter = letter return key for _, group in groupby(string, keyfunc): letters = list(group) length = len(letters) if length > longest_length: longest_length, longest_letters = length, letters return ''.join(longest_letters) print(longest_sorted('hixwluvyhzzzdgd')) print(longest_sorted('eseoojlsuai')) print(longest_sorted('drurotsxjehlwfwgygygxz')) print(longest_sorted('abcdefghijklmnopqrstuvwxyz')) 

SALIDA

 > python3 test.py luvy jlsu ehlw abcdefghijklmnopqrstuvwxyz > 
 s = 'azcbobobegghakl' i=1 subs=s[0] subs2=s[0] while(i=s[j-1]): subs+=s[j] j+=1 else: subs=subs.replace(subs[:len(subs)],s[i]) break if(len(subs)>len(subs2)): subs2=subs2.replace(subs2[:len(subs2)], subs[:len(subs)]) subs=subs.replace(subs[:len(subs)],s[i]) i+=1 print("Longest substring in alphabetical order is:",subs2) 
 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)