Zählen Sie Vokalketten in Bereichen

2559. Zählen Sie Vokalketten in Bereichen

Schwierigkeit:Mittel

Themen:Array, String, Präfixsumme

Sie erhalten ein 0-indiziertes Array von Zeichenfolgenwörtern und ein 2D-Array von Ganzzahlabfragen.

Jede Abfrage query[i] = [l_i, r_i] fordert uns auf, die Anzahl der Zeichenfolgen zu ermitteln, die im Bereich l_i bis vorhanden sind r_i (beide einschließlich) von Wörtern, die mit einem Vokal beginnen und enden.

Gibt ein Array ans der Größe query.length zurück, wobei ans[i] die Antwort auf die i^teAbfrage ist.

Beachten Sie, dass die Vokalbuchstaben „a“, „e“, „i“, „o“ und „u“ sind.

Beispiel 1:

• Eingabe: Wörter = ["aba", "bcb", "ece", "aa", "e"], Abfragen = [[0,2],[1,4],[1, 1]]
• Ausgabe: [2,3,0]
• Erklärung: Die Zeichenfolgen, die mit einem Vokal beginnen und enden, sind „aba“, „ece“, „aa“ und „e“.
  • Die Antwort auf die Abfrage [0,2] ist 2 (Strings „aba“ und „ece“).
  • zur Abfrage von [1,4] sind 3 (Zeichenfolgen „ece“, „aa“, „e“).
  • zur Abfrage von [1,1] ist 0.
  • Wir geben [2,3,0] zurück.

Beispiel 2:

• Eingabe: Wörter = ["a", "e", "i"], Abfragen = [[0,2],[0,1],[2,2]]
• Ausgabe: [3,2,1]
• Erklärung:Jeder String erfüllt die Bedingungen, also geben wir [3,2,1] zurück.

Einschränkungen:

• 1 <= Wörter.Länge <= 10⁵
• 1 <= Wörter[i].Länge <= 40
• Wörter[i] bestehen nur aus englischen Kleinbuchstaben.
• sum(words[i].length) <= 3 * 10⁵
• 1 <= query.length <= 10⁵
• 0 <= l_i <= r_i < Wörter.Länge

Hinweis:

1. Berechnen Sie im Voraus die Präfixsumme der Zeichenfolgen, die mit Vokalen beginnen und enden.
2. Verwenden Sie unordered_set, um Vokale zu speichern.
3. Überprüfen Sie, ob das erste und das letzte Zeichen der Zeichenfolge im Vokalsatz vorhanden sind.
4. Subtrahieren Sie die Präfixsumme für den Bereich [l-1, r], um die Anzahl der Zeichenfolgen zu ermitteln, die mit Vokalen beginnen und enden.

Lösung:

Wir können diesen Schritten folgen:

1. Auf Vokalzeichenfolgen prüfen: Erstellen Sie eine Hilfsfunktion, um festzustellen, ob eine Zeichenfolge mit einem Vokal beginnt und endet.
2. Präfixsummen vorab berechnen:Verwenden Sie ein Präfixsummen-Array, um die kumulative Anzahl von Zeichenfolgen zu speichern, die mit Vokalen beginnen und enden.
3. Antworten auf Abfragen:Verwenden Sie das Präfix-Summen-Array, um die Anzahl solcher Zeichenfolgen innerhalb des angegebenen Bereichs für jede Abfrage effizient zu berechnen.

Lassen Sie uns diese Lösung in PHP implementieren: 2559. Zählen Sie Vokalketten in Bereichen

  
  
  Erläuterung:




isVowelString-Funktion:


Überprüft, ob das erste und das letzte Zeichen der Zeichenfolge Vokale sind.
Verwendet in_array, um zu bestimmen, ob die Zeichen in der vordefinierten Vokalliste enthalten sind.



Präfix-Summen-Array:



prefixSum[i] speichert die kumulative Anzahl der Vokalzeichenfolgen bis zum Index i-1.
Wenn das aktuelle Wort die Bedingung erfüllt, erhöhen Sie die Anzahl.



Abfrageauflösung:


Für einen Bereich [l, r] beträgt die Anzahl der Vokalzeichenfolgen prefixSum[r 1] - prefixSum[l].



Effizienz:


Der Aufbau des Präfix-Summen-Arrays erfordert O(n), wobei n die Anzahl der Wörter ist.
Das Lösen jeder Abfrage erfordert O(1), wodurch sich die Gesamtkomplexität O(n q) ergibt, wobei q ist die Anzahl der Abfragen.





  
  
  Randfälle:



Alle Saiten beginnen und enden mit Vokalen.
Keine Zeichenfolgen beginnen und enden mit Vokalen.
Einzelelementbereiche in den Abfragen.


Dieser Ansatz geht effizient mit den Einschränkungen des Problems um.

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 vonZählen Sie Vokalketten in Bereichen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!