Finde längsten Teilstring in alphabetischer Reihenfolge

Question

Ich möchte ein Programm schreiben, das den längsten Teilstring in alphabetischer Reihenfolge druckt.

Und im Falle von Bindungen, druckt es die erste Teilkette.

Hier ist, was ich schrieb

import sys 
s1 = str(sys.argv[1]) 
alpha = "abcdefghijklmnopqrstuvwxyz" 

def longest_substring(s1): 
    for i in range(len(alpha)): 
     for k in range(len(alpha)): 
      if alpha[i:k] in s1: 
       return alpha[i:k] 

print("Longest substring in alphabetical order:", longest_substring(s1)) 

Allerdings funktioniert es nicht, und ich weiß nicht, wie der zweite Teil zu tun.

Können Sie mir bitte helfen?

Answer 1

Hier ist, was Ihr Code sollte erreichen aussehen mögen, was Sie wollen:

#!/usr/bin/env python3.6 
import sys 
s1 = str(sys.argv[1]) 
alpha = "abcdefghijklmnopqrstuvwxyz" 
subs = [] 


def longest_substring(s1): 
    for i in range(len(alpha)): 
     for k in range(len(alpha)): 
      if alpha[i:k] in s1: 
       subs.append(alpha[i:k]) 
    return max(subs, key=len) 


print("Longest substring in alphabetical order:", longest_substring(s1)) 

Sie wurden direkt aus der Funktion auf der ersten alphabetisch geordnete Rückkehr Teilzeichen Sie gefunden. In meinem Code fügen wir sie zu einer Liste hinzu und drucken dann die längste aus.

Answer 2

Anstatt eine Liste aller möglichen Teilzeichenketten zu erstellen und dann zu prüfen, welche in der Zeichenkette vorhanden ist, können Sie eine Liste aller aufeinanderfolgenden Teilzeichenfolgen erstellen und dann die mit der maximalen Länge verwenden.

Dies ist einfach durch Gruppieren der Zeichen mit dem Unterschied zwischen ord dieses Charakters und einem steigenden Zähler; aufeinander folgende Zeichen werden einen konstanten Unterschied haben. itertools.groupby wird verwendet, um die Gruppierung auszuführen:

from itertools import groupby, count 

alpha = "abcdefghijklmnopqrstuvwxyz" 
c = count() 

lst_substrs = [''.join(g) for _, g in groupby(alpha, lambda x: ord(x)-next(c))] 
substr = max(lst_substrs, key=len) 
print(substr) 
# abcdefghijklmnopqrstuvwxyz 

Als @AdamSmith kommentiert, nimmt das oben die Zeichen immer in alphabetischer Reihenfolge sind. Im Fall können sie nicht sein, kann man die Reihenfolge erzwingen, indem Sie prüfen, ob Elemente in der Gruppe sind alphabetisch:

from itertools import groupby, count, tee 

lst = [] 
c = count() 
for _, g in groupby(alpha, lambda x: ord(x)-next(c)): 
    a, b = tee(g) 
    try: 
     if ord(next(a)) - ord(next(a)) == -1: 
      lst.append(''.join(b)) 
    except StopIteration: 
     pass 
    lst.extend(b) # add each chr from non-alphabetic iterator (could be empty) 

substr = max(lst, key=len) 

Answer 3

Angenommen, String enthält 2 oder mehr Zeichen in alphabetischer Reihenfolge. Damit sollten Sie nicht nur das erste Vorkommnis zurückgeben, sondern alle sammeln und am längsten finden. Ich versuche, Ihre Idee des gleiche zu halten, aber das ist nicht die effizienteste Art und Weise:

def longest_substring(s1): 
    res = [] 
    for i in range(len(alpha) - 2): 
     for k in range(i + 2, len(alpha)): 
      if alpha[i:k] in s1: 
       res.append(alpha[i:k]) 
    return max(res, key=len) 

Answer 4

Sie neu zu schreiben, eine Version von itertools.takewhile einen binären nehmen Funktion anstelle dem einstelligen einer vergleichen.

def my_takewhile(predicate, starting_value, iterable): 
    last = starting_value 
    for cur in iterable: 
     if predicate(last, cur): 
      yield cur 
      last = cur 
     else: 
      break 

Dann können Sie das Wort klein geschrieben (seit "Za" nicht in alphabetischer Reihenfolge ist, aber jede [A-Z] vergleicht lexikographisch vor jedem [a-z]) und alle Teil bekommen.

i = 0 
substrings = [] 
while i < len(alpha): 
    it = iter(alpha[i:]) 
    substring = str(my_takewhile(lambda x,y: x<y, chr(0), it)) 
    i += len(substring) 
    substrings.append(substring) 

Dann finden nur die längste Teilkette in substrings.

result = max(substrings, key=len) 

Answer 5

sichern und dieses Problem erneut untersuchen. 1. Sie sind für eine maximale suchen und im Grunde sollte (Pseudocode):

set a max to "" 
loop through sequences 
    if new sequence is bigger the max, then replace max 

1. die Sequenzen finden Sie effizienter sein kann, wenn man nur einmal wenn die eingegebenen Zeichen Schritt .

Hier ist eine Version davon:

def longest_substring(s1): 
    max_index, max_len = 0, 0 # keep track of the longest sequence here 
    last_c = s1[0] # previous char 
    start, seq_len = 0, 1 # tracking current seqence 

    for i, c in enumerate(s1[1:]): 
     if c >= last_c: # can we extend sequence in alpha order 
      seq_len += 1 
      if seq_len > max_len: # found longer 
       max_index, max_len = start, seq_len 
     else: # this char starts new sequence 
      seq_len = 0 
      start = i + 1 
     last_c = c 
    return s1[max_index:max_index+max_len]