Python 2.7 Finden, ob ein Anagramm einer Zeichenkette eine Teilzeichenkette einer anderen

Question

ist Bearbeiten: Posting meine endgültige Lösung, weil dies ein sehr hilfreicher Thread war, und ich möchte etwas Finalität hinzufügen. Mit dem Ratschlag aus beiden Antworten konnte ich eine Lösung erarbeiten. Ich habe eine Hilfsfunktion hinzugefügt, in der ich ein Anagramm definiert habe. Hier ist meine endgültige Lösung:

def anagram(s1, s2): 
    s1 = list(s1) 
    s2 = list(s2) 
    s1.sort() 
    s2.sort() 
    return s1 == s2 

def Question1(t, s): 
    t_len = len(t) 
    s_len = len(s) 
    t_sort = sorted(t) 
    for start in range(s_len - t_len + 1): 
     if anagram(s[start: start+t_len], t): 
      return True 
    return False 

print Question1("app", "paple") 

---

ich auf einige der Praxis technische Fragen Interview arbeite, und ich bin fest auf folgende Frage:

Find whether an anagram of string t is a substring of s

ich gearbeitet habe, aus den folgenden zwei Varianten meines Codes, und eine Lösung dafür glaube ich liegt in einer Kreuzung zwischen den beiden. Das Problem, das ich habe, ist, dass der erste Code immer False. druckt, unabhängig von der Eingabe. Die zweite Variante funktioniert bis zu einem gewissen Grad. Es kann jedoch nicht einzelne Buchstaben sortieren. Zum Beispiel t=jks s=jksdTrue! jedoch t=kjs s=jksd druckt False.

def Question1(): 
    # Define strings as raw user input. 
    t = raw_input("Enter phrase t:") 
    s = raw_input("Enter phrase s:") 
    # Use the sorted function to find if t in s 
    if sorted(t.lower()) in sorted(s.lower()): 
     print("True!") 
    else: 
     print("False.") 

Question1() 

Arbeits Variante gedruckt wird:

def Question1(): 
    # Define strings as raw user input. 
    t = raw_input("Enter phrase t:") 
    s = raw_input("Enter phrase s:") 
    # use a loop to find if t is in s. 
    if t.lower() in s.lower(): 
     print("True!") 
    else: 
     print("False.") 

Question1() 

Ich glaube, es gibt eine Lösung, die zwischen diesen beiden liegt, aber ich habe Probleme, herauszufinden, wie man Verwenden Sie in dieser Situation sorted.

Answer 1

Sie sind auf dem richtigen Weg sehr viel. Bitte beachten Sie, dass es beim zweiten Versuch keine Schleife gibt.

Das Problem ist, dass Sie nicht einfach alle von s sortieren und dann nach sortierten (t) suchen können. Stattdessen müssen Sie jede len (t) große Teilmenge von s betrachten und diese gegen die sortierten t überprüfen. Betrachten Sie das triviale Beispiel:

t = "abd" 
s = "abdc" 

s enthält triviale t. Wenn Sie sie jedoch sortieren, erhalten Sie die Strings abd und abcd, und der in Vergleich schlägt fehl. Die Sortierung bekommt andere Buchstaben in die Quere.

Stattdessen müssen Sie die Größe t in Stücke durch s treten.

t_len = len(t) 
s_len = len(s) 
t_sort = sorted(t) 
for start in range(s_len - t_len + 1): 
    chunk = s[start:start+t_len] 
    if t_sort == sorted(chunk): 
     # SUCCESS!! 

Answer 2

Ich denke, Ihr Problem liegt in der "substring" Anforderung. Wenn Sie sortieren, zerstören Sie die Ordnung. Das bedeutet, dass Sie zwar feststellen können, dass ein Anagramm von string1 ein Anagramm einer Teilzeichenkette von string2 ist, bis Sie jedoch tatsächlich mit string2 in der richtigen Reihenfolge umgehen, haben Sie keine korrekte Antwort.

Ich würde vorschlagen, über alle Teilstrings der Länge len(s1) in s2 iterieren. Dies ist eine einfache for-Schleife. Sobald Sie die Teilzeichenfolgen haben, können Sie sie (sortiert oder sortiert) mit s1 vergleichen, um zu entscheiden, ob es eine Neuordnung von s1 gibt, die eine zusammenhängende Teilzeichenfolge von s2 ergibt.

Viz:

s1 = "jks" 
s2 = "aksjd" 

print('s1=',s1, ' s2=', s2) 
for offset in range(len(s2) - len(s1) + 1): 
    ss2 = s2[offset:offset+len(s1)] 
    if sorted(ss2) == sorted(s1): 
     print('{} is an anagram of {} at offset {} in {}'.format(ss2, s1, offset, s2))