Check if a string in JavaScript can be a palindrome

Exploring the world of string manipulation in JavaScript reveals a fascinating challenge: determining whether a given string can be converted to a palindrome. Palindromes, where the same word or phrase is read front and back, have an inherent appeal and spark the curiosity of developers seeking to uncover their mysterious properties. In this article, we'll embark on an illuminating journey to uncover the complexities of checking whether a string can turn into a palindrome using the powerful language features and algorithms inherent in JavaScript. By delving into string manipulation and employing innovative techniques, we unravel the mystery of converting strings into palindromes, thereby improving our skills as discerning JavaScript practitioners.

Problem Statement

The current task is to develop a JavaScript algorithm that can efficiently determine whether a given string can be converted into a palindrome by removing just one character. Palindromes remain unchanged when reading forward or backward. The algorithm requires a thorough analysis of the input string, examining its individual characters while considering the option of removing individual characters if a palindrome needs to be created. The output will be a boolean indicating whether the string can be converted to a palindrome. For better understanding, let us consider the following example.

Example input

"racecar"

Example output

true

indicates that the string can indeed be converted to a palindrome by removing at most one character.

method

In this article we will see a number of different ways to solve the above problems in JavaScript -

• Double pointer

• recursion

• Dynamic programming

Method 1: Two pointers

The common problem of checking whether a string can be a palindrome in JavaScript can be solved using the two pointer method. This involves initializing two pointers, one at the beginning of the string and one at the end of the string, comparing the characters at these pointers, and moving them toward the center. To achieve this, define a JavaScript function that takes a string as input and initializes pointers and modifies variables. Then, use a while loop to compare characters, add unmatched modifications, and move the pointer accordingly. After the loop ends, check whether modifications is less than or equal to 1 to determine whether a palindrome can be formed. Finally, a Boolean value is returned indicating whether a palindrome can be created from the string.

Example

canBePalindrome function checks whether the string can be made a palindrome by removing at most one character. It uses a two-pointer approach to iterate over the string and compare characters. If the characters are equal, both pointers move toward the center. If not, it checks if a character can be removed by comparing adjacent characters. Returns false if a character has been removed. If the loop completes without returning false, returns true, indicating that the string can become a palindrome. The example usage at the bottom demonstrates this functionality.

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

The following is the console output -

true
true
true
true
true
false

Method 2: Recursion

To check if you can make a string a palindrome using recursion in JavaScript, define a function called canBePalindrome() that accepts an input string. For the base case, returns true if the length of the string is less than or equal to 1. Otherwise, compare the first and last characters and call canBePalindrome() recursively with the updated string, removing the characters if they are equal. This process is repeated until the base case is reached. Returns false if the first and last characters are not equal. Finally, canBePalindrome() is called with the input string, stores the result, and continues further processing or displays an appropriate message based on the result.

Example

In this code, the canFormPalindrome function accepts a string as input and returns true if the string can become a palindrome by removing at most one character, otherwise it returns false. The isPalindrome function is a helper function that checks whether a substring is a palindrome.

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

The following is the console output -

true
true
false

Method Three: Dynamic Planning

To check if you can convert a string to a palindrome using dynamic programming in JavaScript, define a function called canBePalindrome that takes a string as input. Create a dynamic programming table to store the results of the subproblems. Iterate over the string from both ends using two pointers, comparing the characters at those positions. If they are the same, move the pointer accordingly. If different, check whether the substring between the pointers has been processed in the table. If not, the canBePalindrome function is called recursively on the substring and the result is stored. Consider excluding characters from the left and right pointers, and update the table if either case returns true. After updating the table, return the value stored in the entry that represents the entire string to determine if it can be rearranged into a palindrome. This approach solves problems efficiently by leveraging dynamic programming and decomposing it into sub-problems.

示例

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

The above is the detailed content of Check if a string in JavaScript can be a palindrome. For more information, please follow other related articles on the PHP Chinese website!