Leetcode: Größter gemeinsamer Teiler von Strings

Problemstellung 1071. Größter gemeinsamer Teiler von Strings

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.

Mein Denkprozess

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.

Testfälle

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

Was fehlgeschlagen/erfolgreich war

Ich konnte nur dann eine Lösung finden, wenn:

1. Finden Sie den GCD von zwei Zeichenfolgen.
2. Iterieren Sie von der Länge der kleinsten Zeichenfolge bis zum GCD
3. Nehmen Sie einen Teilstring vom kleinsten String bis zum aktuellen Iterationswert.
4. Wenn beide Zeichenfolgen diese Teilzeichenfolge enthalten, wird diese Teilzeichenfolge als Antwort zurückgegeben.
5. Wenn keine Zeichenfolge gefunden wird, geben Sie „“ zurück.

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:

1. 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.

2. 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.

Ausgabe

Zeit- und Raumkomplexität

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!