Kira Rentetan Vokal dalam Julat

2559. Kira Rentetan Vokal dalam Julat

Kesukaran: Sederhana

Topik: Tatasusunan, Rentetan, Jumlah Awalan

Anda diberi 0-diindeks tatasusunan perkataan rentetan dan tatasusunan 2D pertanyaan integer.

Setiap pertanyaan pertanyaan[i] = [l_i, r_i] meminta kami mencari bilangan rentetan yang terdapat dalam julat l_i hingga r_i (kedua-duanya termasuk) perkataan yang bermula dan berakhir dengan vokal.

Kembalikan tatasusunan ans pertanyaan saiz.panjang, dengan ans[i] ialah jawapan kepada pertanyaan i^ke.

Perhatikan bahawa huruf vokal ialah 'a', 'e', ​​'i', 'o' dan 'u'.

Contoh 1:

• Input: perkataan = ["aba","bcb","ece","aa","e"], pertanyaan = [[0,2],[1,4],[1, 1]]
• Output: [2,3,0]
• Penjelasan: Rentetan yang bermula dan berakhir dengan vokal ialah "aba", "ece", "aa" dan "e".
  • Jawapan kepada pertanyaan [0,2] ialah 2 (rentetan "aba" dan "ece").
  • untuk membuat pertanyaan [1,4] ialah 3 (rentetan "ece", "aa", "e").
  • untuk membuat pertanyaan [1,1] ialah 0.
  • Kami kembali [2,3,0].

Contoh 2:

• Input: perkataan = ["a","e","i"], pertanyaan = [[0,2],[0,1],[2,2]]
• Output: [3,2,1]
• Penjelasan: Setiap rentetan memenuhi syarat, jadi kami kembali [3,2,1].

Kekangan:

• 1 <= perkataan.panjang <= 10⁵
• 1 <= perkataan[i].panjang <= 40
• perkataan[i] hanya terdiri daripada huruf kecil Inggeris.
• jumlah(perkataan[i].panjang) <= 3 * 10⁵
• 1 <= queries.length <= 10⁵
• 0 <= l_i <= r_i < perkataan.panjang

Petunjuk:

1. Prahitung jumlah awalan rentetan yang bermula dan berakhir dengan vokal.
2. Gunakan unordered_set untuk menyimpan vokal.
3. Semak sama ada aksara pertama dan terakhir rentetan terdapat dalam set vokal.
4. Tolak jumlah awalan untuk julat [l-1, r] untuk mencari bilangan rentetan bermula dan berakhir dengan vokal.

Penyelesaian:

Kita boleh ikut langkah ini:

1. Semak Rentetan Vokal: Cipta fungsi pembantu untuk menentukan sama ada rentetan bermula dan berakhir dengan vokal.
2. Jumlah Awalan Prakiraan: Gunakan tatasusunan jumlah awalan untuk menyimpan kiraan kumulatif rentetan yang bermula dan berakhir dengan vokal.
3. Jawapan Pertanyaan: Gunakan tatasusunan jumlah awalan untuk mengira dengan cekap bilangan rentetan sedemikian dalam julat yang ditentukan untuk setiap pertanyaan.

Mari kita laksanakan penyelesaian ini dalam PHP: 2559. Kira Rentetan Vokal dalam Julat

  
  
  Penjelasan:




isVowelString Fungsi:


Menyemak sama ada aksara pertama dan terakhir rentetan ialah vokal.
Menggunakan in_array untuk menentukan sama ada aksara berada dalam senarai vokal yang dipratentukan.



Susun Susun Awalan:



prefixSum[i] menyimpan kiraan kumulatif rentetan vokal sehingga indeks i-1.
Jika perkataan semasa memenuhi syarat, tambahkan kiraan.



Penyelesaian Pertanyaan:


Untuk julat [l, r], kiraan rentetan vokal ialah prefixSum[r 1] - prefixSum[l].



Kecekapan:


Membina tatasusunan jumlah awalan memerlukan O(n), dengan n ialah bilangan perkataan.
Menyelesaikan setiap pertanyaan memerlukan O(1), menjadikan keseluruhan kerumitan O(n q), di mana q ialah bilangan pertanyaan.





  
  
  Kes Tepi:



Semua rentetan bermula dan berakhir dengan vokal.
Tiada rentetan bermula dan berakhir dengan vokal.
Julat elemen tunggal dalam pertanyaan.


Pendekatan ini menangani kekangan masalah dengan cekap.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:


LinkedIn
GitHub



          

            
        
Atas ialah kandungan terperinci Kira Rentetan Vokal dalam Julat. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!