通过将前缀加 1，最小化使字符串成为回文的操作
在本题中，我们将计算通过增加给定字符串的前缀字符所需的操作次数。
我们将使用字符差异来计算使字符串成为回文所需的最少操作次数。
问题描述 - 我们给出了一个包含数字的字符串 nums。我们需要计算将字符串转换为回文串所需的最少操作次数。
在一次操作中，我们可以选择字符串的任意前缀，并将所有前缀字符加 1。
示例
输入
nums = "22434"
输出
2
说明
首先，我们可以选择 22 个前缀，并将所有字符加 1。因此，字符串变成了 33434。
之后，我们可以选择"3"前缀，字符串变成了 43434，这是一个回文字符串。
输入
nums = '151'
输出
0
解释- 该字符串已经是回文字符串。因此，打印 0。
输入
nums = "32102"
输出
-1
解释- 通过增加前缀值无法将字符串转换为回文字符串。
方法 1
如果字符串满足以下两个条件，我们可以根据问题描述将其转换为回文字符串。
将字符串分成两等份后，第一部分的数字应该小于第二部分的数字。
在左侧部分，起始字符应该大于结束字符，因为我们需要选择任意前缀并将每个字符加 1。
算法
步骤 1 - 将 q 初始化为 len - 1，将 p 初始化为 0，因为我们将它们用作索引指针。使用最大整数值初始化 maxOps 来存储最小操作数，并使用 0 初始化 'curr' 来存储最大差值。
步骤 2 - 开始遍历字符串，直到 q > 。 p。
步骤 3 - 如果索引 q 处的字符小于索引 p，则返回 -1，因为无法将字符串转换为回文字符串。
步骤 4 - 将索引 q 和 p 处字符的 ASCII 值之差存储到 'diff' 变量中。
步骤 5 - 将 'curr' 和 'diff' 中的最大值存储到 'curr' 变量中。
步骤 6 - 如果 'maxOps' 值小于 'diff'，则返回 -1。
步骤 7 - 使用 'diff' 值更新 'maxOps'。
步骤 8 - 将 p 加 1，将 q 减 1。
步骤 9 - 返回"curr"值。
示例
#include <bits/stdc++.h>
using namespace std;
int makePalindrome(string alpha, int len) {
int q = len - 1;
int p = 0;
int maxOpes = INT_MAX;
int curr = 0;
// Travere from both ends
while (q > p) {
// 字符串不可能是回文字符串
if (alpha[q] < alpha[p]) {
return -1;
}
// 获取字符差异
int diff = alpha[q] - alpha[p];
// 获取当前最大差异
curr = max(curr, diff);
// 中心处的差异应小于末尾的字符
if (maxOpes < diff) {
return -1;
}
maxOpes = diff;
p++;
q--;
}
return curr;
}
int main() {
string nums = "22434";
int len = nums.length();
cout << "使字符串回文所需的最少操作次数是 " << makePalindrome(nums, len);
return 0;
}
输出
使字符串回文所需的最少操作次数是 2
遍历字符串的时间复杂度为 O(N)。
空间复杂度为 O(1)，因为我们没有使用任何额外的空间。
在解决方案中，我们检查从起始位置到中心的差异，如果中心侧字符的差异较大，则返回 -1。程序员可以尝试从中心遍历字符串，并检查起始侧差异较大的字符。
