Semak sama ada rentetan dalam JavaScript boleh menjadi palindrom

Menerokai dunia manipulasi rentetan dalam JavaScript mendedahkan cabaran yang menarik: menentukan sama ada rentetan tertentu boleh ditukar kepada palindrom. Palindrom, di mana perkataan atau frasa yang sama dibaca depan dan belakang, mempunyai daya tarikan yang wujud dan mencetuskan rasa ingin tahu pembangun yang ingin mendedahkan sifat misteri mereka. Dalam artikel ini, kami akan memulakan perjalanan yang mencerahkan untuk mendedahkan kerumitan menyemak sama ada rentetan boleh bertukar menjadi palindrom menggunakan ciri bahasa dan algoritma yang berkuasa yang wujud dalam JavaScript. Dengan mendalami manipulasi rentetan dan menggunakan teknik inovatif, kami membongkar misteri keajaiban menukar rentetan menjadi palindrom, dengan itu meningkatkan kemahiran kami sebagai pengamal JavaScript yang arif.

Pernyataan Masalah

Tugas semasa adalah untuk membangunkan algoritma JavaScript yang boleh menentukan dengan cekap sama ada rentetan yang diberikan boleh ditukar menjadi palindrom dengan mengalih keluar hanya satu aksara. Palindrom kekal tidak berubah apabila membaca ke hadapan atau ke belakang. Algoritma ini memerlukan analisis menyeluruh bagi rentetan input, memeriksa aksara individunya sambil mempertimbangkan pilihan untuk mengalih keluar aksara individu jika palindrom perlu dibuat. Output akan menjadi boolean yang menunjukkan sama ada rentetan boleh ditukar kepada palindrom. Untuk pemahaman yang lebih baik, mari kita pertimbangkan contoh berikut.

Contoh input

"racecar"

Contoh output

true

menunjukkan bahawa rentetan memang boleh ditukar kepada palindrom dengan mengalih keluar paling banyak satu aksara.

Kaedah

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

• Dua tangan

• Rekursi

• Perancangan Dinamik

Kaedah 1: Dua petunjuk

Masalah biasa untuk menyemak sama ada rentetan boleh menjadi palindrom dalam JavaScript boleh diselesaikan menggunakan kaedah dua penunjuk. Ini melibatkan memulakan dua penunjuk, satu pada permulaan rentetan dan satu pada akhir rentetan, membandingkan aksara pada penunjuk ini dan mengalihkannya ke arah tengah. Untuk mencapai matlamat ini, tentukan fungsi JavaScript yang mengambil rentetan sebagai input dan memulakan penunjuk dan mengubah suai pembolehubah. Kemudian, gunakan gelung sementara untuk membandingkan aksara, tambah pengubahsuaian yang tidak dapat dipadankan dan gerakkan penuding dengan sewajarnya. Selepas gelung tamat, semak sama ada pengubahsuaian kurang daripada atau sama dengan 1 untuk menentukan sama ada palindrom boleh dibentuk. Akhir sekali, nilai Boolean dikembalikan menunjukkan sama ada palindrom boleh dicipta daripada rentetan.

Contoh

Fungsi

canBePalindrome menyemak sama ada rentetan boleh dijadikan palindrom dengan mengalih keluar paling banyak satu aksara. Ia menggunakan pendekatan dua mata untuk mengulangi rentetan dan membandingkan aksara. Jika aksara adalah sama, kedua-dua penunjuk bergerak ke arah tengah. Jika tidak, ia menyemak sama ada aksara boleh dialih keluar dengan membandingkan aksara bersebelahan. Mengembalikan palsu jika aksara telah dialih keluar. Jika gelung selesai tanpa mengembalikan palsu, mengembalikan benar, menunjukkan bahawa rentetan boleh menjadi palindrom. Contoh penggunaan di bahagian bawah menunjukkan fungsi ini.

function canBePalindrome(str) {
   let left = 0;
   let right = str.length - 1;
   let removed = false;
 
   while (left < right) {
      if (str[left] !== str[right]) {
         if (removed) {
            return false; // Already removed a character, can't remove more
         }
         
         // Try removing either the character at the left or right pointer
         if (str[left + 1] === str[right]) {
            left++;
         } else if (str[left] === str[right - 1]) {
            right--;
         } else {
            return false; // Unable to make the string a palindrome by removing one character
         }
      
         removed = true;
      }   
      left++;
      right--;
   }
   return true; // The string can be made a palindrome by removing at most one character
}
 
// Example usage:
console.log(canBePalindrome("racecar")); // true
console.log(canBePalindrome("abccdba")); // true
console.log(canBePalindrome("abccba")); // true
console.log(canBePalindrome("abcdcba")); // true
console.log(canBePalindrome("abcddba")); // false
console.log(canBePalindrome("abcdefg")); // false

Output

Berikut ialah output konsol -

true
true
true
true
true
false

Kaedah 2: Rekursi

Untuk menyemak sama ada anda boleh membuat rentetan palindrom menggunakan rekursi dalam JavaScript, tentukan fungsi yang dipanggil canBePalindrome() yang menerima rentetan input. Untuk kes asas, kembali benar jika panjang rentetan kurang daripada atau sama dengan 1. Jika tidak, bandingkan aksara pertama dan terakhir dan panggil canBePalindrome() secara rekursif dengan rentetan yang dikemas kini, alih keluar aksara jika ia sama. Proses ini diulang sehingga kes asas dicapai. Mengembalikan palsu jika aksara pertama dan terakhir tidak sama. Akhir sekali, canBePalindrome() dipanggil dengan rentetan input, menyimpan hasilnya dan meneruskan pemprosesan selanjutnya atau memaparkan mesej yang sesuai berdasarkan hasilnya.

Contoh

Dalam kod ini, fungsi canFormPalindrome menerima rentetan sebagai input dan mengembalikan benar jika rentetan itu boleh menjadi palindrom dengan mengalih keluar paling banyak satu aksara, jika tidak ia mengembalikan palsu. Fungsi isPalindrome ialah fungsi pembantu yang menyemak sama ada subrentetan ialah palindrom.

function canFormPalindrome(str) {
   // Helper function to check if a substring is a palindrome
   function isPalindrome(left, right) {
      while (left < right) {
         if (str[left] !== str[right]) {
            return false;
         }
         left++;
         right--;
      }
      return true;
   }
 
   // Recursive function to check if the string can be made a palindrome
   function checkPalindrome(left, right) {
      if (left >= right) {
         return true; // Base case: single character or empty string
      }
 
      if (str[left] === str[right]) {
         return checkPalindrome(left + 1, right - 1); // Characters match, check inner substring
      }
 
      // Try removing either left or right character and check the remaining substring
      return isPalindrome(left + 1, right) || isPalindrome(left, right - 1);
   }
 
   // Call the recursive function starting from the endpoints of the string
   return checkPalindrome(0, str.length - 1);
}
 
// Example usage
console.log(canFormPalindrome("abcba")); // true
console.log(canFormPalindrome("abbca")); // true
console.log(canFormPalindrome("abcd")); // false

Output

Berikut ialah output konsol -

true
true
false

Kaedah 3: Pengaturcaraan dinamik

Untuk menyemak sama ada anda boleh menukar rentetan kepada palindrom menggunakan pengaturcaraan dinamik dalam JavaScript, tentukan fungsi yang dipanggil canBePalindrome yang mengambil rentetan sebagai input. Cipta jadual pengaturcaraan dinamik untuk menyimpan hasil submasalah. Lelaran pada rentetan dari kedua-dua hujung menggunakan dua penunjuk, membandingkan aksara pada kedudukan tersebut. Jika ia adalah sama, gerakkan penunjuk dengan sewajarnya. Jika berbeza, semak sama ada subrentetan antara penunjuk telah diproses dalam jadual. Jika tidak, fungsi canBePalindrome dipanggil secara rekursif pada subrentetan dan hasilnya disimpan. Pertimbangkan untuk mengecualikan aksara daripada penunjuk kiri dan kanan, dan kemas kini jadual jika mana-mana kes kembali benar. Selepas mengemas kini jadual, kembalikan nilai yang disimpan dalam entri yang mewakili keseluruhan rentetan untuk menentukan sama ada ia boleh disusun semula menjadi palindrom. Pendekatan ini menyelesaikan masalah dengan cekap dengan memanfaatkan pengaturcaraan dinamik dan menguraikannya kepada sub-masalah.

示例

在此代码中，canFormPalindrome 函数将字符串 str 作为输入，并返回一个布尔值，指示该字符串是否可以通过最多删除一个字符来使该字符串成为回文。该函数使用动态规划表dp来存储中间结果并检查str的所有可能的子串。最后，如果整个字符串可以成为回文，则返回 true，否则返回 false。

function canFormPalindrome(str) {
   const n = str.length;
 
   // Create a 2D dynamic programming table
   const dp = Array(n)
   .fill(false)
   .map(() => Array(n).fill(false));
 
   // Initialize the diagonal to true
   for (let i = 0; i < n; i++) {
      dp[i][i] = true;
   }
 
   // Fill the table diagonally
   for (let len = 2; len <= n; len++) {
      for (let i = 0; i < n - len + 1; i++) {
         const j = i + len - 1;
    
         if (str[i] === str[j]) {
         
            // Characters at the current indices are equal
            dp[i][j] = dp[i + 1][j - 1];
         } else {
         
            // Try removing either the character at index i or j
            dp[i][j] = dp[i + 1][j] || dp[i][j - 1];
         }
      }
   }
 
   // Return true if the whole string can be made a palindrome by removing at most one character
   return dp[0][n - 1];
}
 
// Example usage:
const str = "abca";
const canBePalindrome = canFormPalindrome(str);
console.log(canBePalindrome); 

输出

以下是控制台输出 -

true

结论

总之，确定字符串是否可以使用 JavaScript 转换为回文的过程是一个多方面的工作。通过利用各种字符串操作技术并采用系统方法，人们可以有效地确定实现回文对称的可行性。对字符频率的细致评估以及不常见字符串算法的利用可以带来令人着迷的见解和创造性的解决方案。从事这种智力追求使程序员能够深入研究语言操作的复杂性，从而对语言领域进行令人满意的探索。最终，识别字符串中回文潜力的能力证明了 JavaScript 作为编程语言的独创性和多功能性。

Atas ialah kandungan terperinci Semak sama ada rentetan dalam JavaScript boleh menjadi palindrom. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!