Teilen Sie einen String in die maximale Anzahl eindeutiger Teilstrings auf

1593. Teilen Sie einen String in die maximale Anzahl eindeutiger Teilstrings auf

Schwierigkeit:Mittel

Themen:Hash-Tabelle, String, Backtracking

Geben Sie bei einer gegebenen Zeichenfolge s die maximale Anzahl eindeutiger Teilzeichenfolgen zurück, in die die gegebene Zeichenfolge aufgeteilt werden kann.

Sie können Zeichenfolgen in eine beliebige Liste von nicht leeren Teilzeichenfolgen aufteilen, wobei die Verkettung der Teilzeichenfolgen die ursprüngliche Zeichenfolge bildet. Allerdings müssen Sie die Teilzeichenfolgen so aufteilen, dass sie alle eindeutig sind.

Eine Teilzeichenfolge ist eine zusammenhängende Folge von Zeichen innerhalb einer Zeichenfolge.

Beispiel 1:

• Eingabe: s = "ababccc"
• Ausgabe: 5
• Erklärung: Eine Möglichkeit zur maximalen Aufteilung ist ['a', 'b', 'ab', 'c', 'cc']. Eine Aufteilung wie ['a', 'b', 'a', 'b', 'c', 'cc'] ist nicht gültig, da Sie 'a' und 'b' mehrmals haben.

Beispiel 2:

• Eingabe: s = "aba"
• Ausgabe: 2
• Erklärung: Eine Möglichkeit zur maximalen Aufteilung ist ['a', 'ba'].

Beispiel 3:

• Eingabe: s = "aa"
• Ausgabe: 1
• Erklärung:Es ist unmöglich, die Zeichenfolge weiter aufzuteilen.

Einschränkungen:

• 1
• s enthält nur englische Kleinbuchstaben.

Hinweis:

1. Verwenden Sie einen Satz, um den Überblick darüber zu behalten, welche Teilzeichenfolgen bereits verwendet wurden
2. Probieren Sie jeden möglichen Teilstring an jeder Position aus und gehen Sie zurück, wenn eine vollständige Aufteilung nicht möglich ist

Lösung:

Wir können einen Backtracking-Ansatz verwenden. Dies beinhaltet den rekursiven Versuch, Teilzeichenfolgen aus der aktuellen Position in der Zeichenfolge zu erstellen und die eindeutigen Teilzeichenfolgen zu verfolgen, die wir bisher verwendet haben.

Hier ist eine Schritt-für-Schritt-Lösung:

1. Rekursive Funktion: Erstellen Sie eine Funktion, die alle möglichen Teilzeichenfolgen beginnend mit dem aktuellen Index der Zeichenfolge untersucht.
2. Auf Eindeutigkeit festlegen: Verwenden Sie einen Satz (oder ein Array in PHP), um die eindeutigen Teilzeichenfolgen zu verfolgen, die im aktuellen Rekursionspfad verwendet wurden.
3. Backtracking: Wenn ein Teilstring ausgewählt wird, können wir mit der Auswahl des nächsten Teilstrings fortfahren. Wenn wir einen Punkt erreichen, an dem keine weiteren Teilzeichenfolgen ohne Wiederholung gebildet werden können, kehren wir zurück.
4. Basisfall: Wenn wir das Ende der Zeichenfolge erreichen, zählen wir die gebildeten eindeutigen Teilzeichenfolgen.

Lassen Sie uns diese Lösung in PHP implementieren: 1593. Teilen Sie einen String in die maximale Anzahl eindeutiger Teilstrings auf

<?php class Solution {

    /**
     * @param String $s
     * @return Integer
     */
    function maxUniqueSplit($s) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * @param $s
     * @param $used
     * @param $start
     * @return int|mixed
     */
    private function backtrack($s, $used, $start) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }
}

// Example usage
$solution = new Solution();
echo $solution->maxUniqueSplit("ababccc"); // Output: 5
echo "\n";
echo $solution->maxUniqueSplit("aba"); // Output: 2
echo "\n";
echo $solution->maxUniqueSplit("aa"); // Output: 1
?>

Erläuterung:

1. Funktionssignatur: Die Hauptfunktion ist maxUniqueSplit, die den Backtracking-Prozess initialisiert.

2. Zurückverfolgen:

   • Die Backtrack-Funktion übernimmt den String, das Array der verwendeten Teilstrings und den aktuellen Startindex.
   • Wenn der Startindex das Ende der Zeichenfolge erreicht, gibt er die Anzahl der gesammelten eindeutigen Teilzeichenfolgen zurück.
   • Eine Schleife durchläuft mögliche Endindizes, um Teilzeichenfolgen aus dem Startindex zu erstellen.
   • Wenn die Teilzeichenfolge eindeutig ist (nicht bereits im verwendeten Array), wird sie zu „verwendet“ hinzugefügt und die Funktion führt eine Rekursion für den nächsten Index durch.
   • Nachdem dieser Pfad erkundet wurde, wird die Teilzeichenfolge entfernt, um zurückzugehen und andere Möglichkeiten zu erkunden.

3. Ausgabe: Die Funktion gibt die maximale Anzahl eindeutiger Teilzeichenfolgen für verschiedene Eingabezeichenfolgen zurück.

Komplexität

• Die zeitliche Komplexität kann aufgrund der Art des Backtracking hoch sein, insbesondere bei längeren Strings, aber angesichts der Einschränkungen (maximale Länge von 16) ist diese Lösung effizient genug für die Eingabegrenzen.

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 vonTeilen Sie einen String in die maximale Anzahl eindeutiger Teilstrings auf. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!