通过递增子字符串的所有字符将字符串转换为回文串的最小移动次数

---

在计算机科学和编程领域，发现有效的算法来解决问题非常重要。一个有趣的问题是确定将字符串转换为回文串所需的最小操作次数，方法是增加子字符串中的所有字符。本文探讨了两种使用 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”，然后将此值打印到控制台。

结论

以下文本中提供了两种替代解决方案，旨在提供洞察力和潜在答案，以解决计算通过子字符串中字符操作将给定字符串转换为回文串所需的移动次数的障碍。一种称为暴力法的方法包含所有可能的子字符串，而另一种称为最佳双指针方法的方法则大大减少了所需的移动次数。程序员可以轻松地应用这些机制来解决类似的障碍，并相应地提升他们的解决方案。