Kira subrentetan yang sepadan dalam JavaScript

Keupayaan untuk mengira subrentetan padanan dengan tepat dalam rentetan tertentu adalah kemahiran utama dalam pengaturcaraan JavaScript, kerana ia membolehkan pembangun menganalisis dan memanipulasi data teks dengan cekap. Artikel ini menyelidiki dunia manipulasi rentetan dan meneroka kerumitan mengira subrentetan padanan dalam JavaScript, menggunakan satu siri teknik yang kurang diketahui. Dengan menjelaskan logik asas dan menggunakan kaedah tidak konvensional ini, pembangun boleh memperoleh pemahaman yang lebih mendalam tentang cara mengira kejadian subrentetan tertentu dengan cekap, membolehkan mereka mengekstrak cerapan bermakna daripada data teks. Sertai kami dalam perjalanan yang memberi inspirasi ini sambil kami membuka potensi kuasa JavaScript dan mengembangkan perbendaharaan kata kami yang kaya untuk menguasai seni mengira subrentetan padanan.

Pernyataan Masalah

Kami memerlukan fungsi JavaScript yang mengira urutan dalam rentetan tertentu dan mengambil input rentetan bernama "str" ​​​​dan tatasusunan input rentetan bernama "arr". Matlamatnya adalah untuk memeriksa setiap elemen dalam "arr" dan menentukan bilangan rentetan yang merupakan susulan daripada "str". Susunan ialah rentetan yang dibentuk dengan mengalih keluar aksara daripada rentetan asal sambil mengekalkan susunan relatif aksara yang tinggal. Fungsi harus membandingkan dengan teliti setiap elemen dalam "arr" dan "str" ​​​​dan menentukan sama ada ia boleh dibina dengan mengalih keluar aksara daripada "str". Ia kemudiannya akan mengembalikan integer yang mewakili kiraan urutan yang layak ditemui dalam "str".

Contoh input -

str = 'abracadabra';
arr = ['a', 'bra', 'cad', 'dab'];

Contoh output -

Output =4;

Huraian output -

Dalam input yang diberikan, rentetan "str" ​​​​ ialah "abracadabra" dan tatasusunan "arr" mengandungi ['a', 'bra', 'cad', 'dab'].

Menganalisis setiap elemen "arr", kami mendapati bahawa "a", "bra", "cad" dan "dab" semuanya adalah susulan daripada "str". Oleh itu, kiraan susulan ialah 4, iaitu output yang dijangkakan.

Kaedah

Dalam artikel ini kita akan melihat beberapa cara berbeza untuk menyelesaikan masalah di atas dalam JavaScript -

• Kaedah brute force cracking

• Kaedah double pointer

Kaedah 1: Brute force cracking

Pendekatan kekerasan untuk mengira urutan yang sah melibatkan penjanaan semua kemungkinan urutan rentetan dan menyemak kehadirannya dalam tatasusunan. Kami mengulangi setiap rentetan, menjana urutan secara rekursif atau menggunakan operasi bitwise, dan membandingkannya dengan elemen tatasusunan. Kaunter dinaikkan setiap perlawanan, memberikan jumlah kiraan. Kaedah ini adalah mahal dari segi pengiraan untuk input yang lebih besar, jadi algoritma alternatif seperti pengaturcaraan dinamik menyediakan penyelesaian yang lebih optimum.

Contoh

Kod ini melaksanakan algoritma rekursif untuk mengira bilangan urutan rentetan (str) yang diberikan dalam tatasusunan rentetan (arr). Fungsi countSubsequences memulakan pembolehubah kiraan untuk menjejaki urutan yang sah. Fungsi generateSubsequences menjana semua kemungkinan susulan dengan mengulangi rentetan input dan menyemak sama ada setiap urutan hadir dalam tatasusunan. Panggilan rekursif dibuat untuk meneroka kemungkinan berbeza untuk memasukkan atau mengecualikan aksara. Panggilan fungsi utama menjana urutan bermula dari permulaan rentetan. Pembolehubah kiraan dikembalikan sebagai hasil akhir. Contoh Penggunaan menunjukkan penggunaan fungsi ini dengan rentetan sampel dan tatasusunan rentetan. Hasilnya disimpan dan dicetak ke konsol.

function countSubsequences(str, arr) {
   let count = 0;
 
   // Generate all possible subsequences of the input string
   function generateSubsequences(sub, index) {
      if (index === str.length) {
         // Check if the subsequence exists in the array
         if (arr.includes(sub)) {
            count++;
         }
         return;
      }
 
      // Include the current character in the subsequence
      generateSubsequences(sub + str[index], index + 1);
 
      // Exclude the current character from the subsequence
      generateSubsequences(sub, index + 1);
   }
 
   // Start generating subsequences from the beginning of the string
   generateSubsequences("", 0);
 
   return count;
}
 
// Example usage:
const str = "abcde";
const arr = ["a", "ab", "bd", "abc", "acde", "eab"];
const result = countSubsequences(str, arr);
console.log(result);

Output

Berikut ialah output konsol -

5

Kaedah 2: Kaedah dua mata

Algoritma melelaran melalui setiap rentetan dalam tatasusunan dan menggunakan dua penunjuk, satu ditetapkan untuk rentetan yang diberikan dan satu lagi untuk rentetan yang sedang diperiksa. Penunjuk ini pada mulanya terletak pada aksara permulaan rentetan sepadannya dan kemudian maju ke hadapan sehingga penghujung mana-mana rentetan ditemui. Setiap kali urutan yang sah ditentukan, penunjuk berangka akan dinaikkan. Akhirnya, algoritma menyediakan nilai berangka penunjuk sebagai hasil akhir.

Contoh

Fungsi countValidSubsequences mengambil tatasusunan rentetan (arr) dan rentetan sasaran (sasaran) sebagai parameter. Ia berulang pada setiap rentetan dalam arr dan membandingkan aksaranya dengan yang berada dalam sasaran menggunakan gelung bersarang. Jika aksara sepadan, indeks ditambah jika ia tidak sepadan, hanya indeks sasaran ditambah. Jika keseluruhan rentetan ialah urutan yang sah, kiraan akan ditambah. Selepas melelaran melalui semua rentetan dalam arr, fungsi mengembalikan kiraan akhir.

function countValidSubsequences(arr, target) {
   let count = 0;
 
   for (let i = 0; i < arr.length; i++) {
      const current = arr[i];
      let j = 0;
      let k = 0;
 
      while (j < current.length && k < target.length) {
         if (current[j] === target[k]) {
            j++;
            k++;
         } else {
            k++;
         }
      }
 
      if (j === current.length) {
         count++;
      }
   }
 
   return count;
}
 
// Example usage: 
const str = "abcde"; 
const arr = ["a", "ab", "bd", "abc", "acde", "eab"]; 
const result = countValidSubsequences(arr, str); 
console.log(result);

Output

Berikut ialah output konsol -

5

Kesimpulan

Akhirnya, penerokaan pengiraan subrentetan padanan dalam JavaScript ini menemui beberapa teknik pintar yang boleh digunakan untuk menyelesaikan tugas ini dengan cekap. Dengan menggunakan pelbagai algoritma dan memanfaatkan ciri bahasa yang jarang digunakan, pengaturcara boleh mereka bentuk penyelesaian yang elegan dan bijak. Perlu diakui bahawa kerumitan pemadanan subrentetan memerlukan pertimbangan yang teliti terhadap kes tepi dan potensi kesan prestasi. Walau bagaimanapun, dengan cerapan baharu ini, pembangun boleh melangkaui pendekatan tradisional dan memanfaatkan potensi penuh JavaScript untuk menghitung dan memanipulasi subrentetan dengan bijak. Secara keseluruhan, pengetahuan mendalam yang dikongsi dalam artikel ini membolehkan pengaturcara meningkatkan kebolehan pengekodan mereka dan membuka kunci dimensi baharu pengiraan subrentetan dalam JavaScript.

Atas ialah kandungan terperinci Kira subrentetan yang sepadan dalam JavaScript. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!