Zusätzliche Zeichen in einer Zeichenfolge

2707. Zusätzliche Zeichen in einer Zeichenfolge

Schwierigkeit:Mittel

Themen: Array, Hash-Tabelle, String, dynamische Programmierung, Trie

Sie erhalten eine 0-indizierte Zeichenfolge und ein Wörterbuch mit Wörtern. Sie müssen s in einen oder mehrere nicht überlappende Teilzeichenfolgen aufteilen, sodass jede Teilzeichenfolge im Wörterbuch vorhanden ist. Es kann einige zusätzliche Zeichen in s geben, die in keinem der Teilstrings vorhanden sind.

Geben Sie die Mindestanzahl zusätzlicher Zeichen zurück, die übrig bleiben, wenn Sie s optimal aufteilen.

Beispiel 1:

• Eingabe: s = „leetscode“, dictionary = [„leet“, „code“, „leetcode“]
• Ausgabe: 1
• Erklärung: Wir können s in zwei Teilzeichenfolgen aufteilen: „leet“ von Index 0 bis 3 und „code“ von Index 5 bis 8. Es gibt nur 1 unbenutztes Zeichen (bei Index 4), also geben wir 1 zurück .

Beispiel 2:

• Eingabe: s = „sayhelloworld“, dictionary = [„hello“, „world“]
• Ausgabe: 3
• Erklärung: Wir können s in zwei Teilzeichenfolgen aufteilen: „hello“ von Index 3 bis 7 und „world“ von Index 8 bis 12. Die Zeichen an den Indizes 0, 1, 2 werden in keiner Teilzeichenfolge verwendet und werden daher als zusätzliche Zeichen betrachtet. Daher geben wir 3 zurück.

Einschränkungen:

• 1
• 1
• 1
• dictionary[i] und s bestehen nur aus englischen Kleinbuchstaben
• Wörterbuch enthält verschiedene Wörter

Hinweis:

1. Können wir hier dynamische Programmierung verwenden?
2. Definieren Sie DP[i] als minimales zusätzliches Zeichen, wenn Sie s[0:i] optimal aufteilen möchten.

Lösung:

Wir können ein dp-Array definieren, wobei dp[i] die minimale Anzahl zusätzlicher Zeichen in der Teilzeichenfolge s[0:i] nach optimaler Segmentierung darstellt.

Ansatz:

1. Dynamische Programmierdefinition:

   • Sei dp[i] die minimale Anzahl zusätzlicher Zeichen in der Teilzeichenfolge s[0:i].
   • Um dp[i] zu berechnen, können wir:
     • Betrachten Sie entweder das Zeichen s[i-1] als zusätzliches Zeichen und gehen Sie zum nächsten Index.
     • Oder prüfen Sie, ob im Wörterbuch eine Teilzeichenfolge vorhanden ist, die mit dem Index i endet, und wenn ja, verwenden Sie sie, um zusätzliche Zeichen zu reduzieren.

2. Übergang:

   • Für jeden Index i gilt Folgendes:
     • Fügen Sie eins zu dp[i-1] hinzu, wenn wir s[i] als zusätzliches Zeichen behandeln.
     • Überprüfen Sie jeden möglichen Teilstring s[j:i] (für j

3. Ergebnis:

   • Der Wert von dp[len(s)] gibt uns die Mindestanzahl zusätzlicher Zeichen in der gesamten Zeichenfolge s.

Lassen Sie uns diese Lösung in PHP implementieren: 2707. Zusätzliche Zeichen in einer Zeichenfolge

<?php /**
 * @param String $s
 * @param String[] $dictionary
 * @return Integer
 */
function minExtraChar($s, $dictionary) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo minExtraChar("leetscode", ["leet","code","leetcode"]); // Output: 1
echo "\n";
echo minExtraChar("sayhelloworld", ["hello","world"]); // Output: 3
?>

Erläuterung:

1. Basisfall:

   • dp[0] = 0, da in einer leeren Zeichenfolge keine zusätzlichen Zeichen vorhanden sind.

2. Wörterbuchsuche:

   • Wir speichern die Wörterbuchwörter in einer Hash-Map mit array_flip() für eine zeitkonstante Suche.

3. Übergang:

   • Für jede Position i prüfen wir alle möglichen Teilzeichenfolgen s[j:i]. Wenn im Wörterbuch ein Teilstring vorhanden ist, aktualisieren wir den dp[i]-Wert.

4. Zeitkomplexität:

   • Die zeitliche Komplexität beträgt O(n^2), wobei n die Länge der Zeichenfolge s ist, da wir für jeden Index alle vorherigen Indizes überprüfen, um Teilzeichenfolgen zu bilden.

Testergebnisse:

Für die Eingabe „leetscode“ mit dem Wörterbuch [„leet“, „code“, „leetcode“] gibt die Funktion korrekt 1 zurück, da nur noch 1 zusätzliches Zeichen („s“) übrig bleibt.

Für die Eingabe „sayhelloworld“ mit Wörterbuch [„hello“, „world“] gibt die Funktion 3 zurück, da die ersten drei Zeichen („say“) extra sind.

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 vonZusätzliche Zeichen in einer Zeichenfolge. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!