C++ 将字符串string1中的字符按照字典顺序递增或递减转换为字符串string2中的字符

在这个问题中，程序员需要通过递增或递减操作，使str1中的所有字符都等于str2中的任何一个字符。同时，我们可以进行环形递增或递减操作。也就是说，’z’ + 1 ‘a’，’a’ – 1 ‘z’。

我们可以通过找到将str1字符串的字符变为str2字符串的任何字符所需的最小代价来解决这个问题。对于每个字符，我们可以找到最小所需的操作次数，并将它们相加。

问题陈述 - 给定两个名为str1和str2的字符串。str1的大小为N，str2的大小为M。另外，给定条件是N<=M或N>M。两个字符串只包含小写字母字符。任务是通过递增或递减操作，使str1的所有字符都等于str2的任何一个字符。我们需要找到使str1的所有字符等于str2的任何一个字符所需的最小操作次数。

示例

输入

str1 = "aedc", str2 = "db";

输出

3

解释

• 我们可以使 ‘a’ 等于 ‘b’，成本为 1。

• 我们可以使 ‘e’ 等于 ‘d’，成本为 1。

• ‘d’ 在 str2 中已经存在，所以成本为 0。

• 我们可以使 ‘c’ 等于 b 或 d，成本将为 1。

因此，所需总成本或所需操作的次数为 3。

输入

str1 = "mwerd", str2 = "dermw";

输出

0

解释 - str1的所有字符都存在于str2中。所以，所需操作数等于零。

输入

str1 = "bdfhjlnp", str2 = "acegikmo";

输出

8

解释 – 我们可以通过将str1的每个字符增加或减少1来使其等于str2的任何字符。例如，‘b’ -> ‘a’，‘d’ -> ‘c’或‘d’ -> ‘e’等。

方法

我们将取str1字符串的任何字符，并通过执行增加或减少操作将其变为str2的每个字符。然后，我们将找到使str1的每个字符的最小成本，并将它们相加。

让我们了解将一个字符变为另一个字符的两种方法。

• 将字符‘a’转换为‘e’。

• 通过增加，我们需要4次操作使‘a’等于‘e’。

• 通过减少操作，我们需要26 – 4 = 22次操作。

这里，4是最小值，所以我们将考虑它。

• 将字符‘a’转换为‘y’。

• 通过增加，我们需要24次操作。

• 通过减少，我们需要2次操作。

所以，最少需要的操作次数是4。

算法

步骤1 – 定义名为unordered hashmap的‘str2Chars’，用于存储str2字符串的字符频率。

步骤2 – 遍历字符串并更新哈希图中每个字符的频率。

步骤3 – 定义‘count’变量以存储最少需要的操作次数。

步骤4 – 开始遍历字符串1。在循环中，用最大整数值初始化minMoves变量，以存储使第p个字符等于str2任何字符所需的最小操作次数。

步骤5 – 使用循环进行1到26次迭代。通过从str1[p]中减去‘a’获得0到25之间的char值。

步骤6 – 如果当前字符存在于哈希图中，则将minMoves变量赋值为零并终止循环。

步骤7 – 否则，如果哈希图中存在‘a’ + q字符，则我们可以将第p个字符转换为‘a’ + q。

步骤8 – 通过增加操作获取使字符等于‘a’ + q的总操作次数，并将其存储在leftMin变量中。

步骤9 – 同样，通过减少操作找到使字符等于‘a’ + q的总操作次数，并将其存储在rightMin变量中。

步骤10 – 从‘leftMin’和‘rightMin’中获取最小值。同时，还要从allMoves和minMoves中获取最小值。

第11步 - 将minMoves添加到count变量的值中。

第12步 - 返回’count’的值。

示例

#include <bits/stdc++.h>
using namespace std;

int totalOps(string str1, string str2) {
    // Map to store all characters of str2
    unordered_map<char, int> str2Chars;
    // Traverse str2
    for (int p = 0; p < str2.size(); p++) {
        str2Chars[str2[p]]++;
    }
    // Store minimum operations
    int count = 0;
    // Traverse str1
    for (int p = 0; p < str1.size(); p++) {
        // Total minimum move requires converting one character to another
        int minMoves = INT_MAX;
        // Calculate required moves
        for (int q = 0; q < 26; q++) {
            // Get the character value
            int char_val = str1[p] - 'a';
            // If str2 contains the str1[p]
            if (str2Chars[str1[p]] > 0) {
                minMoves = 0;
                break;
            } else if (str2Chars['a' + q] > 0) {
                // Find minimum difference between str1[p] and str2[q]
                int leftMin = abs(char_val - q);
                int RightMin = min((26 - char_val) + q, char_val + (26 - q));
                int allMoves = min(leftMin, RightMin);
                minMoves = min(minMoves, allMoves);
            }
        }
        // Update minimum operations
        count += minMoves;
    }
    // Return total operations
    return count;
}
int main() {
    string str1 = "aedc";
    string str2 = "db";
    cout << "The minimum numbers of operations required to convert str1 to str2 is " << totalOps(str1, str2);
    return 0;
}

输出

The minimum numbers of operations required to convert str1 to str2 is 3

时间复杂度 – O(N*26) ~ O(N)，因为我们要遍历字符串。

空间复杂度 – O(1)，因为我们不使用恒定的空间。

类似地，程序员可以尝试解决要使str2全部等于str1的问题。因此，我们需要在将str1中的第p个索引处字符转换为str2中的第p个索引处字符时，取增量或减量操作的最小值。