Leerzeichen zu einer Zeichenfolge hinzufügen

2109. Leerzeichen zu einer Zeichenfolge hinzufügen

Schwierigkeit:Mittel

Themen:Array, Zwei Zeiger, String, Simulation

Sie erhalten eine 0-indizierte Zeichenfolge s und ein 0-indiziertes Ganzzahl-Array „spaces“, das die Indizes in der ursprünglichen Zeichenfolge beschreibt, an denen Leerzeichen hinzugefügt werden. Jedes Leerzeichen sollte vor dem Zeichen am angegebenen Index eingefügt werden.

• Wenn beispielsweise s = „EnjoyYourCoffee“ und Leerzeichen = [5, 9] sind, platzieren wir Leerzeichen vor „Y“ und „C“, die sich auf den Indizes 5 bzw. 9 befinden. So erhalten wir „Enjoy Your Coffee“.

Gib die geänderte Zeichenfolge zurück, nachdemdie Leerzeichen hinzugefügt wurden.

Beispiel 1:

• Eingabe: s = "LeetcodeHelpsMeLearn", Leerzeichen = [8,13,15]
• Ausgabe: „Leetcode hilft mir beim Lernen“
• Erklärung: Die Indizes 8, 13 und 15 entsprechen den unterstrichenen Zeichen in „LeetcodeHelpsMeLearn“.
  • Wir setzen dann Leerzeichen vor diese Zeichen.

Beispiel 2:

• Eingabe: s = "icodeinpython", Leerzeichen = [1,5,7,9]
• Ausgabe: „Ich codiere in Python“
• Erklärung: Die Indizes 1, 5, 7 und 9 entsprechen den unterstrichenen Zeichen in „icodeinpython“.
  • Wir setzen dann Leerzeichen vor diese Zeichen.

Beispiel 3:

• Eingabe: s = "spacing", Leerzeichen = [0,1,2,3,4,5,6]
• Ausgabe: „ s p a c i n g“
• Erklärung:Wir können auch Leerzeichen vor dem ersten Zeichen der Zeichenfolge platzieren.

Einschränkungen:

• 1 <= s.length <= 3 * 10⁵
• s besteht nur aus englischen Klein- und Großbuchstaben.
• 1 <= Leerzeichen.Länge <= 3 * 10⁵
• 0 <= Leerzeichen[i] <= s.length - 1
• Alle Werte von Leerzeichen sind strikt ansteigend.

Hinweis:

1. Erstellen Sie eine neue, zunächst leere Zeichenfolge als geänderte Zeichenfolge. Durchlaufen Sie die ursprüngliche Zeichenfolge und hängen Sie jedes Zeichen der ursprünglichen Zeichenfolge an die neue Zeichenfolge an. Fügen Sie jedoch jedes Mal, wenn Sie ein Zeichen erreichen, vor dem ein Leerzeichen erforderlich ist, ein Leerzeichen ein, bevor Sie das Zeichen anhängen.
2. Da das Array der Indizes für die Leerstellen sortiert ist, verwenden Sie einen Zeiger, um den nächsten Index zum Platzieren eines Leerzeichens zu verfolgen. Erhöhen Sie den Zeiger erst, wenn ein Leerzeichen angehängt wurde.
3. Stellen Sie sicher, dass Ihr Anhängevorgang in O(1) durchgeführt werden kann.

Lösung:

Wir können einen effizienten Ansatz mit zwei Hinweisen verwenden. So würde die Implementierung in PHP 5.6 aussehen:

Lösungserklärung:

1. Verwenden Sie einen Zeiger-SpaceIndex, um die aktuelle Position im Leerzeichen-Array zu verfolgen.
2. Durchlaufen Sie die Zeichenfolge s mithilfe einer Schleife.
3. Überprüfen Sie, ob der aktuelle Index in der Zeichenfolge mit dem aktuellen Wert im Leerzeichen-Array übereinstimmt. Wenn dies der Fall ist, fügen Sie ein Leerzeichen an das Ergebnis an und bewegen Sie den spaceIndex-Zeiger nach vorne.
4. Fügen Sie das aktuelle Zeichen der Zeichenfolge an das Ergebnis an.
5. Gibt das Endergebnis als einzelne Zeichenfolge zurück.

Dieser Ansatz stellt sicher, dass wir die Eingabe effizient verarbeiten und dabei die sortierte Reihenfolge des Leerzeichen-Arrays nutzen.

Lassen Sie uns diese Lösung in PHP implementieren: 2109. Leerzeichen zu einer Zeichenfolge hinzufügen

  
  
  Erläuterung:




Effizientes Anhängen: Die . Der Operator in PHP wird zum effizienten Anhängen von Zeichenfolgen verwendet.

Zwei Zeiger: Der spaceIndex-Zeiger stellt sicher, dass wir das Leerzeichen-Array nur einmal verarbeiten.

Zeitkomplexität:


Das Iterieren über die Zeichenfolge erfordert O(n), wobei n die Länge der Zeichenfolge ist.
Die Prüfung anhand des Leerzeichen-Array-Zeigers erfordert O(m), wobei m die Länge des Leerzeichen-Arrays ist.
Kombiniert: O(n m), was angesichts der Einschränkungen optimal ist.




Diese Lösung hält sich an die Einschränkungen und ist auch bei großen Eingaben effizient.

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 vonLeerzeichen zu einer Zeichenfolge hinzufügen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!