檢查 JavaScript 中的字串是否可以成為回文

探索 JavaScript 中的字串操作領域揭示了一個令人著迷的挑戰：確定給定的字串是否可以轉換為回文。回文，即正反讀相同的單字或短語，具有固有的吸引力，並激發了尋求揭開其神秘屬性的開發人員的好奇心。在本文中，我們將踏上一段啟發性的旅程，揭開使用 JavaScript 固有的強大語言功能和演算法來檢查字串是否可以變成回文的複雜性。透過深入研究字串操作並採用創新技術，我們解開了將字串轉換為回文奇蹟的謎團，從而提高了我們作為挑剔的 JavaScript 從業者的技能。

問題陳述

目前的任務是開發一種 JavaScript 演算法，該演算法可以有效地確定給定字串是否可以透過僅刪除一個字元來轉換為回文。向前或向後讀時，回文保持不變。該演算法需要徹底分析輸入字串，檢查其各個字符，同時考慮在需要創建回文時刪除單個字符的選項。輸出將是一個布林值，指示字串是否可以轉換為回文。為了更好地理解，讓我們考慮以下範例。

範例輸入

"racecar"

範例輸出

true

表示字串確實可以透過刪除最多一個字元來轉換為回文。

方法

在本文中，我們將看到多種不同的方法來解決 JavaScript 中的上述問題 -

• 雙指標

• #遞迴

• 動態規劃

方法一：兩個指標

在 JavaScript 中檢查字串是否可以成為回文的常見問題可以使用兩個指標方法來解決。這涉及初始化兩個指針，一個位於字串的開頭，另一個位於字串的末尾，比較這些指針處的字符，並將它們移向中心。要實現此目的，請定義一個 JavaScript 函數，該函數將字串作為輸入並初始化指標和修改變數。然後，使用 while 循環比較字符，增加不匹配的修改，並相應地移動指針。循環結束後，檢查modifications是否小於等於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

方法二：遞迴

要檢查是否可以使用 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

方法三：動態規劃

要檢查是否可以使用 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 作为编程语言的独创性和多功能性。

以上是檢查 JavaScript 中的字串是否可以成為回文的詳細內容。更多資訊請關注PHP中文網其他相關文章！