在 JavaScript 中检查字符串是否可以变成回文

---

探索 JavaScript 中字符串操作的领域揭示了一个引人入胜的挑战：确定给定的字符串是否可以转换为回文。回文是指正读和反读都相同的单词或短语，它们具有内在的魅力，并激发了开发人员的好奇心，他们寻求揭开其神秘的特性。在本文中，我们踏上了一段启迪之旅，以揭开使用 JavaScript 固有的强大语言特性和算法检查字符串是否可以转换为回文的复杂性。通过深入研究字符串操作的深度并采用创新技术，我们揭开了将字符串转换为回文奇观的谜团，从而提高我们作为有洞察力的 JavaScript 从业者的技能。

问题陈述

手头的任务是开发一种 JavaScript 算法，该算法可以有效地确定给定的字符串是否可以通过仅删除一个字符来转换为回文。回文在正读和反读时保持不变。该算法需要彻底分析输入字符串，检查其各个字符，同时考虑如果需要创建回文则可以选择删除单个字符。输出将是一个布尔值，指示字符串是否可以转换为回文。为了更好地理解，让我们考虑以下示例。

示例输入

"racecar"

示例输出

true

表示该字符串确实可以通过删除最多一个字符转换为回文。

方法

在本文中，我们将看到在 JavaScript 中解决上述问题陈述的多种不同方法：

• 双指针

• 递归

• 动态规划

方法 1：双指针

在 JavaScript 中检查字符串是否可以构成回文的常见问题可以使用双指针方法解决。这涉及初始化两个指针，一个位于字符串的开头，另一个位于字符串的结尾，比较这些指针处的字符，并将它们向中心移动。为了实现这一点，定义一个 JavaScript 函数，该函数以字符串作为输入并初始化指针和修改变量。然后，使用 while 循环比较字符，对于不匹配的字符递增修改，并相应地移动指针。循环结束后，检查修改是否小于或等于 1 以确定是否可以形成回文。最后，返回一个布尔值，指示从字符串创建回文的可能性。

示例

canBePalindrome 函数检查字符串是否可以通过删除最多一个字符来构成回文。它使用双指针方法迭代字符串并比较字符。如果字符相等，则两个指针都向中心移动。如果不是，则通过比较相邻字符来检查是否可以删除字符。如果已经删除了一个字符，则返回 false。如果循环完成而没有返回 false，则返回 true，表示字符串可以构成回文。底部的示例用法演示了该函数。

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

输出

以下是控制台输出：

true
true
true
true
true
false

方法 2：递归

要使用 JavaScript 中的递归检查字符串是否可以构成回文，请定义一个名为 canBePalindrome() 的函数，该函数采用输入字符串。对于基本情况，如果字符串的长度小于或等于 1，则返回 true。否则，比较第一个和最后一个字符，如果它们相等，则使用更新的字符串递归调用 canBePalindrome()，方法是删除这些字符。重复此过程，直到达到基本情况。如果第一个和最后一个字符不相等，则返回 false。最后，使用输入字符串调用 canBePalindrome()，存储结果，并根据结果继续进行进一步处理或显示适当的消息。

示例

在此代码中，canFormPalindrome 函数以字符串作为输入，如果该字符串可以通过删除最多一个字符变为回文，则返回 true，否则返回 false。isPalindrome 函数是用于检查子字符串是否为回文的辅助函数。

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

输出

以下是控制台输出：

true
true
false

方法 3：动态规划

要使用 JavaScript 中的动态规划检查字符串是否可以转换为回文，请定义一个名为 canBePalindrome 的函数，该函数以字符串作为输入。创建一个动态规划表来存储子问题的结果。使用两个指针从字符串的两端迭代，比较这些位置的字符。如果它们相同，则相应地移动指针。如果它们不同，则检查指针之间的子字符串是否已在表中处理过。如果没有，则递归调用 canBePalindrome 函数对子字符串进行操作并存储结果。考虑从左右指针中排除字符，如果任一情况返回 true，则更新表。更新表后，返回代表整个字符串的条目中存储的值，以确定它是否可以重新排列成回文。这种方法通过利用动态规划并将问题分解成子问题来有效地解决问题。

示例

在此代码中，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 作为编程语言的独创性和多功能性。