Für zwei Zeichenfolgen s und t sagen wir „t teilt s“ genau dann, wenn s = t + t + t + ... + t + t (d. h. t ist ein- oder mehrmals mit sich selbst verkettet).
Gegeben zwei Strings str1 und str2, gib den größten String x zurück, sodass x sowohl str1 als auch str2 teilt.
Obwohl der Leetcode es als leichtes Problem markierte, muss ich zugeben, dass es mir schwer fiel, sofort eine Lösung zu finden.
Lassen Sie mich die von Leetcode bereitgestellten Testfälle überprüfen und durchgehen, um meine Verwirrung zu erklären.
Eingabe: str1 = „ABCABC“, str2 = „ABC“
Ausgabe: „ABC“Eingabe: str1 = „ABABAB“, str2 = „ABAB“
Ausgabe: „AB“
Anhand der Problemstellung und des Testfalls 1 habe ich festgestellt, dass wir die größte Zeichenfolge („ABC“) ausgeben müssen, indem wir sie verketten, um beide Zeichenfolgen zu erhalten. (Standardzeichenfolge „ABC“ === str2 und „ABC“ + „ABC“ === str1).
Als ich mir jedoch Testfall 2 ansah, wurde mir schnell klar, dass ich nicht richtig verstanden hatte, dass ich „ABAB“ ausgeben sollte, da dies die längste Zeichenfolge ist, mit der ich beide Zeichenfolgen erstellen kann. Aber ich sprang zum Code und fing an, eine Lösung zu finden. (Anfängerfehler?)
Ich konnte nur dann eine Lösung finden, wenn:
Wie Sie sehen, ist meine Lösung für die Zeichenfolgen fehlgeschlagen, bei denen str1 str2, aber auch einige andere zusätzliche Zeichen enthält. Verstoß gegen die Anforderung, dass s = t + t + ... + t + t.
Ich musste mich an die Lösung von neetcode wenden, um Hilfe zu erhalten. Ich habe meine Probleme schnell verstanden:
Ich habe den GCD der Länge der Zeichenfolge ermittelt, NICHT die Zeichenfolge selbst. Ich muss eine Zeichenfolge finden, bei der ich durch Wiederholen dieser Zeichenfolgen beide Zeichenfolgen ohne verbleibende Zeichen erstellen kann.
Mir wurde klar, warum „ABAB“ nicht die Antwort für Testfall 2 sein kann:
Wir müssen x so finden, dass es beide Strings gleichmäßig teilt. Wenn Sie also „ABAB“ als Zeichenfolge verwenden, können Sie str2 vollständig erstellen, aber für str1 erhalten Sie am Ende „ABABABAB“. Sie erhalten am Ende 2 überschüssige „AB“ und können nicht sagen, dass Sie str1 vollständig durch die Kombination von x erstellt haben.
„ABAB“ Länge 4 und „ABABAB“ Länge 6. Der GCD der beiden Strings = 2. Daher muss die Ausgabe ein String der Länge 2 sein.
Zeitkomplexität:
Im schlimmsten Fall iterieren wir über Min(str1,str2) und müssen str1 und str2 neu erstellen, sodass (str1.length + str2.length) also die Gesamtzeit entsteht Die Komplexität beträgt O(min(str1,str2) * (str1.length + str2.length))Raumkomplexität:
O(1) da wir keinen zusätzlichen Raum benötigen.Das obige ist der detaillierte Inhalt vonLeetcode: Größter gemeinsamer Teiler von Strings. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!