透過遞增子字串的所有字元將字串轉換為迴文串的最小移動次數

---

在計算機科學和程式設計領域，發現有效的演算法來解決問題非常重要。一個有趣的問題是確定將字串轉換為迴文串所需的最小操作次數，方法是增加子字串中的所有字元。本文探討了兩種使用 C++ 程式語言處理此問題的方法。

語法

在深入研究這些方法之前，讓我們定義我們將使用的函式的語法 -

int minMovesToMakePalindrome(string str);

演算法

• 我們的目標是最小化將字串轉換為迴文串的移動次數——我們的演算法透過以下關鍵階段解決此問題 -

• 首先從字串的不同側開始建立兩個指標變數——左指標從字串開頭開始，右指標從字串結尾開始。

• 只要配置限制允許，繼續我們的過程，即一旦任一指標超過另一個指標，則停止 -

• 當字元值相同時，繼續將兩個指標移到一起。當字元值不同時，在保持任何進一步操作之前，將右側的字元（透過它們的差值）增加。這種增加與'a'和'c'之間的差值成正比，因此如果str[right]等於'c'，而str[left]等於'a'，我們將str[right]增加2（因為'a'-'c'=2）。相應地更新移動計數。

• 一旦左指標大於右指標，字串就會轉換為迴文串。

方法 1：暴力法

在這種方法中，我們將考慮所有可能的子字串並計算每個子字串所需的最小移動次數。最後，我們將返回所有計算出的移動次數中的最小值。

示例

#include <iostream>
#include <string>
using namespace std;

int minMovesToMakePalindrome(string str) {
   int moves = 0;
   int length = str.length();

   for (int i = 0; i < length / 2; i++) {
      moves += abs(str[i] - str[length - i - 1]);
   }

   return moves;
}

int main() {
   string str = "abcde";
   int minMoves = minMovesToMakePalindrome(str);
   cout << "Minimum moves to make the string palindrome: " << minMoves << endl;

   return 0;
}

輸出

Minimum moves to make the string palindrome: 6

解釋

建立了一個名為 minMovesToMakePalindrome 的函式，該函式將輸入字串 str 轉換為迴文串，並需要最少的移動次數。我們已經在下面解釋了它是如何透過一些分步說明工作的 -

我們將 moves 變數初始化為 0，它負責跟蹤所需的總移動次數。- 由於 length 變數記錄輸入字串的長度 str，因此我們的下一個操作是使用 for 迴圈迭代半個字串，以便對稱位置不重疊。- 最後，在此迴圈內，abs(str[i] - str[length - i - 1]) 計算兩端字元的絕對差值。

計算出的差值表示使這些位置的字元相等所需的移動次數。我們將此差值新增到移動計數中。

在遍歷所有必要的位置後，我們將所需的總最小移動次數儲存在 moves 變數中。我們返回此值。

在主函式中，我們用值“abcde”初始化一個字串 str。然後，我們呼叫 minMovesToMakePalindrome 函式，並將 str 作為引數傳遞。返回的最小移動次數儲存在 minMoves 變數中。最後，我們將結果列印到控制檯。

方法 2：最佳雙指標方法

此方法利用兩個指標同時從兩端遍歷字串。考慮到效率，我們採用了一種將字串轉換為迴文串的技術，該技術涉及穩定地增加和匹配輸入兩端的字元。這種方法最大限度地減少了多餘的操作，並且可以在不影響準確性或功能的情況下更快地進行轉換。

示例

#include <iostream>
#include <string>
using namespace std;

int minMovesToMakePalindrome(string str) {
   int moves = 0;
   int left = 0;
   int right = str.length() - 1;

   while (left <= right) {
      moves += abs(str[right] - str[left]);
      left++;
      right--;
   }

   return moves;
}

int main() {
   string str = "abcde";
   int minMoves = minMovesToMakePalindrome(str);
   cout << "Minimum moves to make the string palindrome: " << minMoves << endl;

   return 0;
}

輸出

Minimum moves to make the string palindrome: 6

解釋

以下程式碼示例的目標是利用最佳的雙指標方法來確定將給定字串轉換為迴文串所需的最小移動次數。

為此。我們建立一個名為 minMovesToMakePalindrome 的函式。它接受一個字串引數並返回所需的總移動次數。首先，我們將用於計算移動次數的變數設定為 0，並初始化左右兩個指標：左指標從輸入字串的開頭（索引 0）開始，右指標從結尾（索引 str.length() - 1）開始。

我們的 while 迴圈迭代直到左指標大於或等於右指標，以覆蓋字串中的所有元素。在每次迭代中。我們使用 abs(str[right] - str[left]) 找到左指標和右指標位置的字元之間的差值，它表示使這兩個字元相同所需的移動次數。我們將此差值新增到我們用於總移動次數的執行計數中。

隨著我們向輸入字串的中心移動，增加左指標並減少右指標。一旦左指標和右指標之間沒有重疊。我們已經將字串轉換為迴文串。

此時，我們返回儲存在“moves”中的總移動次數計數。在 main() 中，與之前相同，我們宣告一個新的輸入字串“abcde”，使用此引數呼叫 minMovesToMakePalindrome，它返回總最小移動次數值，該值分配給新變數“minMoves”，然後將此值列印到控制檯。

結論

以下文字中提供了兩種替代解決方案，旨在提供洞察力和潛在答案，以解決計算透過子字串中字元操作將給定字串轉換為迴文串所需的移動次數的障礙。一種稱為暴力法的方法包含所有可能的子字串，而另一種稱為最佳雙指標方法的方法則大大減少了所需的移動次數。程式設計師可以輕鬆地應用這些機制來解決類似的障礙，並相應地提升他們的解決方案。