Mindestzeichenfolgenlänge nach dem Entfernen von Teilzeichenfolgen

2696. Mindestzeichenfolgenlänge nach dem Entfernen von Teilzeichenfolgen

Schwierigkeit:Einfach

Themen:String, Stack, Simulation

Sie erhalten eine Zeichenfolge, die nur aus Großbuchstaben englischen Buchstaben besteht.

Sie können einige Operationen auf diese Zeichenfolge anwenden, bei denen Sie in einer Operation jedes Vorkommen einer der Teilzeichenfolgen „AB“ oder „CD“ aus s. entfernen können.

Gib die minimale mögliche Länge der resultierenden Zeichenfolge zurück, die Sie erhalten können.

Beachten Sie, dass die Zeichenfolge nach dem Entfernen der Teilzeichenfolge verkettet wird und neue „AB“- oder „CD“-Teilzeichenfolgen erzeugen können.

Beispiel 1:

• Eingabe: s = "ABFCACDB"
• Ausgabe: 2
• Erklärung: Wir können die folgenden Vorgänge ausführen:
  • Entfernen Sie die Teilzeichenfolge „ABFCACDB“, also s = „FCACDB“.
  • Entfernen Sie die Teilzeichenfolge „FCACDB“, also s = „FCAB“.
  • Entfernen Sie die Teilzeichenfolge „FCAB“, also s = „FC“.
  • Die resultierende Länge der Zeichenfolge beträgt also 2.
  • Es kann gezeigt werden, dass dies die minimale Länge ist, die wir erreichen können.

Beispiel 2:

• Eingabe: s = "ACBBD"
• Ausgabe: 5
• Erklärung: Wir können keine Operationen an der Zeichenfolge ausführen, daher bleibt die Länge gleich.

Einschränkungen:

• 1
• s besteht nur aus englischen Großbuchstaben.

Hinweis:

1. Können wir rohe Gewalt anwenden, um das Problem zu lösen?
2. Durchlaufen Sie die Zeichenfolge wiederholt, um die Teilzeichenfolgen „AB“ und „CD“ zu finden und zu entfernen, bis keine Vorkommen mehr vorhanden sind.

Lösung:

Wir verwenden einen Stapel, um das Entfernen der Teilzeichenfolgen „AB“ und „CD“ zu handhaben. Der Stack-Ansatz stellt sicher, dass wir diese Teilstrings effizient entfernen, wenn sie beim Durchlaufen des Strings auftreten.

Ansatz:

1. Verwenden Sie einen Stapel:
   • Durchlaufen Sie die Zeichenfolge Zeichen für Zeichen.
   • Schiebe jedes Zeichen auf den Stapel.
   • Wenn die beiden obersten Zeichen auf dem Stapel die Teilzeichenfolge „AB“ oder „CD“ bilden, entfernen Sie diese beiden Zeichen aus dem Stapel (entfernen).
   • Setzen Sie diesen Vorgang für alle Zeichen in der Eingabezeichenfolge fort.
2. Letzte Zeichenfolge:
   • Am Ende des Durchlaufs enthält der Stapel die reduzierte Zeichenfolge.
   • Die minimal mögliche Länge entspricht der Größe des Stapels.

Lassen Sie uns diese Lösung in PHP implementieren: 2696. Mindestzeichenfolgenlänge nach dem Entfernen von Teilzeichenfolgen

<?php <br>
/**

• @param String $s
• @return Integer /

function minLengthAfterRemovals($s) { ... ... ... /*

• go to ./solution.php */

}

// Example usage:
echo minLengthAfterRemovals("ABFCACDB"); // Output: 2
echo "\n";
echo minLengthAfterRemovals("ACBBD"); // Output: 5
?>

Erklärung:

• Wir initialisieren einen leeren Stapel ($stack).
• Durchlaufen Sie jedes Zeichen der Zeichenfolge s.
• Überprüfen Sie das oberste Zeichen des Stapels:
  • Wenn das oberste Zeichen und das aktuelle Zeichen die Teilzeichenfolgen „AB“ oder „CD“ bilden, entfernen wir das oberste Zeichen mit array_pop.
  • Andernfalls schieben Sie das aktuelle Zeichen auf den Stapel.
• Der Stapel enthält die Zeichen, die nach allen möglichen Entfernungen übrig bleiben.
• Abschließend gibt count($stack) die Länge der resultierenden Zeichenfolge an.

Komplexität:

• Zeitkomplexität: O(n), wobei n die Länge der Zeichenfolge ist. Jedes Zeichen wird höchstens zweimal verarbeitet (einmal gedrückt, einmal gepoppt).
• Raumkomplexität: O(n) für den Stapel, im schlimmsten Fall, wenn keine Entfernungen möglich sind.

Diese Lösung minimiert die Zeichenfolge effektiv, indem alle möglichen Vorkommen von „AB“ und „CD“ entfernt werden, bis nichts mehr gefunden werden kann.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:

• LinkedIn
• GitHub

Das obige ist der detaillierte Inhalt vonMindestzeichenfolgenlänge nach dem Entfernen von Teilzeichenfolgen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!