Program JavaScript untuk mencari putaran rentetan terkecil dari segi leksikografi

Kami akan mencari putaran rentetan terkecil dari segi leksikografik dalam JavaScript. Kaedah ini melibatkan penggabungan rentetan asal dengan dirinya sendiri dan kemudian menggunakan fungsi "isih" terbina dalam untuk mengisih rentetan bercantum dalam tertib menaik. Akhir sekali, kami akan mengembalikan subrentetan terkecil rentetan bercantum yang diisih dengan panjang yang sama dengan rentetan asal. Ini akan menjadi putaran rentetan terkecil dalam susunan leksikografi.

Kami akan melaksanakan logik ini dengan menggunakan teknik manipulasi rentetan dan fungsi terbina dalam yang tersedia dalam JavaScript. Hasil daripada pelaksanaan kami akan menjadi rentetan yang mewakili putaran minimum rentetan input secara leksikografi. Ini berguna untuk membandingkan dan menyusun rentetan dengan cara yang cekap.

Pada masa hadapan, kami akan terus menambah baik algoritma untuk menjadikannya lebih pantas dan cekap untuk mencari putaran rentetan terkecil dari segi leksikografi.

Kaedah

Di sini dijelaskan cara mencari putaran rentetan terkecil dari segi leksikografi dalam 5 baris -

• Sambungkan rentetan asal dengan dirinya sendiri untuk memastikan semua kemungkinan putaran dipertimbangkan.

• Cari aksara pertama yang tidak sama dengan aksara seterusnya, yang akan digunakan sebagai titik permulaan untuk putaran minimum.

• Jika tiada aksara seperti itu ditemui, rentetan asal dikembalikan kerana ia sudah diputar secara minimum.

• Mengembalikan subrentetan dalam rentetan bercantum bermula dari aksara yang ditemui ke penghujung rentetan sebagai putaran minimum.

• Subrentetan yang dihasilkan akan menjadi putaran terkecil rentetan dalam susunan leksikografi.

Contoh

Putaran rentetan terkecil dari segi leksikografi boleh didapati dengan menggabungkan rentetan asal dengan dirinya sendiri dan mencari subrentetan terkecil yang bermula dengan aksara pertama rentetan asal.

Berikut ialah contoh yang dilaksanakan dalam JavaScript -

function findLexicographicallyMinimumStringRotation(str) {
   let strDouble = str + str;
   let len = str.length;
   let minRotation = strDouble.substring(0, len);
   for (let i = 1; i < len; i++) {
      let currRotation = strDouble.substring(i, i + len);
      if (currRotation < minRotation) {
         minRotation = currRotation;
      }
   }
   return minRotation;
}
const str = 'eadbc';
console.log(findLexicographicallyMinimumStringRotation(str));

Arahan

• Pertama, kami menggabungkan rentetan asal dengan dirinya sendiri untuk mendapatkan strDouble.

• Kami juga mentakrifkan pembolehubah len untuk menyimpan panjang rentetan asal.

• Kemudian kita mulakan minRotation dengan subrentetan pertama panjang len dalam strDouble, iaitu strDouble >.substring(0, len). Ini adalah titik permulaan kami untuk mencari putaran rentetan terkecil dari segi leksikografi.

• Kami kemudian menggunakan gelung for untuk mengulangi semua subrentetan panjang yang mungkin len dalam strDouble bermula dari aksara kedua.

• Untuk setiap lelaran, kita dapati putaran semasa Putaran curr dengan mendapatkan subrentetan panjang len daripada strDouble, dari kedudukan semasa i.

• Jika currRotation kurang daripada minRotation, kami akan mengemas kini minRotation dengan putaran semasa.

• Akhir sekali, selepas gelung for tamat, kami mengembalikan nilai minRotation, iaitu putaran terkecil dari segi leksikografi rentetan.

Atas ialah kandungan terperinci Program JavaScript untuk mencari putaran rentetan terkecil dari segi leksikografi. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!