在 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 作為程式語言的獨創性和多功能性。