C++ 通过增加子字符串中的所有字符，使字符串变成回文所需的最小移动次数

在计算机科学和编程领域，找到解决问题的有效算法非常重要。一个有趣的问题是通过增加子字符串中的所有字符来识别将字符串转换为回文所需的最小操作次数。本文深入探讨了使用C++编程语言处理此问题的两种方法。

语法

在介绍方法之前，让我们定义一下我们将使用的函数的语法−

int minMovesToMakePalindrome(string str);

步骤

我们的目标是在将字符串转换为回文时尽量减少移动次数 – 我们的算法通过以下关键阶段来实现 –
首先建立两个指针变量，一个从字符串的开头开始，另一个从字符串的末尾开始。
只要限制条件允许，即其中一个指针超过另一个指针，就继续进行我们的过程。
每当它们的字符值相同时，将两个指针向彼此靠近。每当字符值不同时，在进行任何进一步的操作之前，将右侧的字符值增加（通过它们的差异）。这种增加与’a’和’c’之间的差异成比例，因此如果str[right]等于’c’且str[left]等于’a’，我们将增加str[right] 2（因为’a’ – ‘c’ = 2）。相应地更新移动次数。
一旦left大于right，字符串就被转换为回文。

方法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计数中。

在遍历所有必要位置之后，我们将所需的总最小操作次数存储在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循环迭代直到left大于或等于right，以覆盖字符串中的所有元素。在每次迭代中，我们使用abs(str[right] – str[left])找到位置left和right处的字符之间的差异，它表示使这两个字符相同所需的移动次数。我们将这个差值加到我们的总移动次数的累加中。

当我们向输入字符串的中心移动时，递增左指针并递减右指针。一旦左右指针之间没有重叠，我们就将字符串转换为回文。

此时，我们返回存储在’moves’中的总移动次数。在main()中，重复之前的相同步骤，我们声明一个新的输入字符串’abcde’，使用这个参数调用minMovesToMakePalindrome，返回的最小移动次数值分配给新变量’minMoves’，然后将这个值打印到控制台上。

结论

以下文本提供了两种备选解决方案，旨在提供关于如何通过在子字符串中进行字符操作来计算将给定字符串转换为回文所需的移动次数的见解和潜在答案。一种方法称为暴力法，包括所有可能的子字符串；另一种方法称为最佳双指针法，大大减少了所需的移动次数。开发人员可以轻松地应用这些机制来解决类似的障碍，并以此提升他们的解决方案。