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

Gegebene 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 sie durchgehen, um meine Verwirrung zu erklären.

Testfälle

Eingabe: str1 = „ABCABC“, str2 = „ABC“
Ausgabe: „ABC“

Eingabe: str1 = „ABABAB“, str2 = „ABAB“
Ausgabe: „AB“

Aus der Problemstellung und dem Testfall 1 habe ich festgestellt, dass wir die größte Zeichenfolge („ABC“) ausgeben müssen, indem wir beide Zeichenfolgen verketten. (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 der längste String ist, mit dem ich beide Strings erstellen kann. Aber ich sprang zum Code und fing an, eine Lösung zu finden. (Anfängerfehler?)

Was fehlgeschlagen/erfolgreich war

Ich konnte nur eine Lösung finden, bei der:

1. Finden Sie den GCD von zwei Zeichenfolgen.
2. Iterieren Sie von der Länge der kleinsten Zeichenfolge bis zum GCD
3. Nimm 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 gefunden, NICHT die Zeichenfolge selbst. Ich muss eine Zeichenfolge finden, in 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 haben 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) die Gesamtzeitkomplexität ergibt wird O(min(str1,str2) * (str1.length str2.length))

Raumkomplexität: O(1), da wir keinen zusätzlichen Raum benötigen.