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

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

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

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);