通过递增子字符串的所有字符，使字符串回文所需的最小移动次数

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

语法

在深入探讨这些方法之前，让我们先定义一下我们将要使用的函数的语法 −

int minMovesToMakePalindrome(string str);

算法

• 我们的目标是在将字符串转换为回文时尽量减少移动次数-这个问题是我们的算法通过以下关键阶段来解决的−

• 首先，从字符串的两侧分别建立两个指针变量，左指针从字符串的开头开始，右指针从字符串的末尾开始。

• Continue our process as long as configuration limits allow i.e. once either pointer surpasses the other halt −

• 每当字符值相同时，继续将两个指针靠拢。每当字符值不同时，在进行任何进一步操作之前，将右侧的字符值增加（根据它们的差异）。这种增加与'a'和'c'之间的差异成比例，因此如果str[right]等于'c'且str[left]等于'a'，我们将str[right]增加2（因为'a'-'c'=2）。相应地更新移动计数。

• 一旦左边大于右边，字符串就会变成回文。

方法一：暴力破解

在这种方法中，我们将考虑所有可能的子字符串，并计算每个子字符串所需的最小移动次数。最后，我们将返回所有计算出的移动次数中的最小值。

Example

#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

Explanation

的翻译为：

解释

已创建一个名为 minMovesToMakePalindrome 的函数，它将输入字符串 str 转换为需要的最小移动次数的回文。我们通过一些逐步说明来解释它的工作原理：

我们将moves变量初始化为0，它负责跟踪所需的总移动次数。- 由于length变量记录了输入字符串str的长度，我们的下一步是使用for循环迭代一半的字符串，以便对称位置不重叠。- 最后，在此循环内部，abs(str[i] - str[length - i - 1])计算两端字符之间的绝对差异。

计算出的差异代表了使这些位置上的字符相等所需的移动次数。我们将这个差异添加到移动计数中。

在迭代所有必要的位置后，我们将所需的总最小移动次数存储在moves变量中。我们返回这个值。

在主函数中，我们用值"abcde"初始化了一个字符串str。然后，我们调用minMovesToMakePalindrome函数，将str作为参数传递进去。返回的最小移动次数存储在minMoves变量中。最后，我们将结果打印到控制台。

方法二：最优的双指针方法

这种方法利用两个指针同时从字符串的两端遍历。考虑到效率，我们采用了一种将字符串转化为回文的技术，该技术涉及从输入的两端逐渐增加和匹配字符。这种方法最大程度地减少了不必要的操作，并且在不影响准确性或功能性的情况下，允许更快的转换。

Example

#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

Explanation

的翻译为：

解释

下面代码示例的目标是利用最优的双指针方法来确定将给定字符串转化为回文所需的最小移动次数。

为了实现这一点，我们创建了一个名为minMovesToMakePalindrome的函数。该函数接受一个字符串参数并返回所需的移动总数。首先，我们将用于计算移动次数的变量设置为0，并初始化左右指针：左指针从输入字符串的开头（索引0）开始，右指针从末尾（索引str.length() - 1）开始。

我们的while循环在left大于等于right之前迭代，以覆盖字符串中的所有元素。在每次迭代中，我们通过使用abs(str[right] - str[left])找到left和right位置的字符之间的差异，这表示需要多少次移动才能使这两个字符相同。我们将这个差异值添加到我们的运行计数器中，以获得总移动次数。

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

At this point we return our count of total moves stored in 'moves'. In main() identical steps are followed as previously where we declare a new input string 'abcde' call minMovesToMakePalindrome with this argument which returns total minimum move count value that's assigned to new variable 'minMoves' before printing this value onto the console.

结论

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

以上是通过递增子字符串的所有字符，使字符串回文所需的最小移动次数的详细内容。更多信息请关注PHP中文网其他相关文章！