将字符串1中的字符转换为字符串2中存在的字符，方法是按字典顺序递增或递减。

在这个问题中，程序员需要通过执行增量或减量操作来使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

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

方法1

我们将取str1字符串的任何字符，并通过执行增量或减量操作使其等于str2的每个字符。之后，我们将找到str1每个字符的最小成本并将它们全部相加。

让我们了解使一个字符等于另一个字符的两种方法。

  • 将字符'a'转换为'e'。

  • 通过递增，我们需要4次操作才能使'a'等于'e'。

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

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

  • 将字符'a'转换为'y'。

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

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

因此，所需的最小操作次数为4。

算法

步骤1 – 定义名为'str2Chars'的无序哈希映射来存储str2字符串中字符的频率。

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

步骤3 – 定义'count'变量来存储所需的最小操作次数。

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

步骤5 – 使用循环进行1到26次迭代。通过从str1[p]中减去'a'来获取0到25之间的字符值。

步骤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'值。

示例

Open Compiler
#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个索引处的字符。

更新于：2023年8月24日

65 次查看

开启您的职业生涯

通过完成课程获得认证

开始学习
广告