最小化使两个给定字符串互为置换所需的给定操作数
给定两个字符串str1和str2，任务是对两个字符串之一进行以下三种类型的最小操作数计数，使str1和str2彼此置换：
-
在字符串中插入一个字符。
-
从字符串中删除一个字符。
-
用字符串中的另一个字符替换一个字符。
注意：所有上述操作成本相同。
示例：
输入：
str1 = "geeksforgeeks", str2 = "geeksforcoder"输出：4
说明：将字符串
str2重新排列为"geeksforcedor"。将
str1[8]的值替换为c。将
str1[10]的值替换为d。将
str1[11]的值替换为o。将
str1[12]的值替换为r。因此，所需的输出为 4。
输入：
str1 = "geek", str2 = "keeg"输出：1
方法：可以使用哈希存储两个字符串的每个字符的频率来解决该问题。 以下是解决该问题的观察结果：
X为字符串str1和str2中都存在的字符数。
N1 – X为仅出现在str1中的字符数。
N2 – X为仅在str2中存在的字符数。替换操作总数为
min(N1 - X, N2 - X)。插入/删除总数为
max(N1 - X, N2-X) - min(N1 - X, N2 - X)。因此，操作总数为
max(N1 - X, N2 - X)，
请按照以下步骤解决问题：
-
初始化两个数组，例如
freq1[]和freq2[]，以存储str1和str2的所有字符的频率。 -
遍历两个字符串，并将两个字符串的每个字符的频率分别存储在数组
freq1[]和freq2[]中。 -
遍历两个数组
freq1[]和freq2[]。 -
对于第
i个字符，如果freq1[i]超过freq2[i]，则将freq1[i]替换为freq1[i] – freq2[i]并设置freq2[i] = 0，反之亦然。
下面是实现上述方法的方法：
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to minimize the count of
// operations to make str1 and str2
// permutations of each other
int ctMinEdits(string str1, string str2)
{
int N1 = str1.length();
int N2 = str2.length();
// Store the frequency of
// each character of str1
int freq1[256] = { 0 };
for (int i = 0; i < N1; i++) {
freq1[str1[i]]++;
}
// Store the frequency of
// each character of str2
int freq2[256] = { 0 };
for (int i = 0; i < N2; i++) {
freq2[str2[i]]++;
}
// Traverse the freq1[] and freq2[]
for (int i = 0; i < 256; i++) {
// If frequency of character in
// str1 is greater than str2
if (freq1[i] > freq2[i]) {
freq1[i] = freq1[i]
- freq2[i];
freq2[i] = 0;
}
// Otherwise
else {
freq2[i] = freq2[i]
- freq1[i];
freq1[i] = 0;
}
}
// Store sum of freq1[]
int sum1 = 0;
// Store sum of freq2[]
int sum2 = 0;
for (int i = 0; i < 256; i++) {
sum1 += freq1[i];
sum2 += freq2[i];
}
return max(sum1, sum2);
}
// Driver Code
int main()
{
string str1 = "geeksforgeeks";
string str2 = "geeksforcoder";
cout << ctMinEdits(str1, str2);
}
Java
// Java program to implement
// the above approach
import java.util.*;
import java.io.*;
import java.lang.Math;
class GFG{
// Function to minimize the count of
// operations to make str1 and str2
// permutations of each other
static int ctMinEdits(String str1, String str2)
{
int N1 = str1.length();
int N2 = str2.length();
// Store the frequency of
// each character of str1
int freq1[] = new int[256];
Arrays.fill(freq1, 0);
for(int i = 0; i < N1; i++)
{
freq1[str1.charAt(i)]++;
}
// Store the frequency of
// each character of str2
int freq2[] = new int[256];
Arrays.fill(freq2, 0);
for(int i = 0; i < N2; i++)
{
freq2[str2.charAt(i)]++;
}
// Traverse the freq1[] and freq2[]
for(int i = 0; i < 256; i++)
{
// If frequency of character in
// str1 is greater than str2
if (freq1[i] > freq2[i])
{
freq1[i] = freq1[i] - freq2[i];
freq2[i] = 0;
}
// Otherwise
else
{
freq2[i] = freq2[i] - freq1[i];
freq1[i] = 0;
}
}
// Store sum of freq1[]
int sum1 = 0;
// Store sum of freq2[]
int sum2 = 0;
for(int i = 0; i < 256; i++)
{
sum1 += freq1[i];
sum2 += freq2[i];
}
return Math.max(sum1, sum2);
}
// Driver Code
public static void main(final String[] args)
{
String str1 = "geeksforgeeks";
String str2 = "geeksforcoder";
System.out.println(ctMinEdits(str1, str2));
}
}
// This code is contributed by bikram2001jha
Python3
# Python3 program to implement
# the above approach
# Function to minimize the count of
# operations to make str1 and str2
# permutations of each other
def ctMinEdits(str1, str2):
N1 = len(str1)
N2 = len(str2)
# Store the frequency of
# each character of str1
freq1 = [0] * 256
for i in range(N1):
freq1[ord(str1[i])] += 1
# Store the frequency of
# each character of str2
freq2 = [0] * 256
for i in range(N2):
freq2[ord(str2[i])] += 1
# Traverse the freq1[] and freq2[]
for i in range(256):
# If frequency of character in
# str1 is greater than str2
if (freq1[i] > freq2[i]):
freq1[i] = freq1[i] - freq2[i]
freq2[i] = 0
# Otherwise
else:
freq2[i] = freq2[i] - freq1[i]
freq1[i] = 0
# Store sum of freq1[]
sum1 = 0
# Store sum of freq2[]
sum2 = 0
for i in range(256):
sum1 += freq1[i]
sum2 += freq2[i]
return max(sum1, sum2)
# Driver Code
str1 = "geeksforgeeks"
str2 = "geeksforcoder"
print(ctMinEdits(str1, str2))
# This code is contributed by code_hunt
C
// C# program to implement
// the above approach
using System;
class GFG{
// Function to minimize the count of
// operations to make str1 and str2
// permutations of each other
static int ctMinEdits(string str1, string str2)
{
int N1 = str1.Length;
int N2 = str2.Length;
// Store the frequency of
// each character of str1
int[] freq1 = new int[256];
freq1[0] = str1[0];
for(int i = 0; i < N1; i++)
{
freq1[str1[i]]++;
}
// Store the frequency of
// each character of str2
int[] freq2 = new int[256];
freq2[0] = str2[0];
for(int i = 0; i < N2; i++)
{
freq2[str2[i]]++;
}
// Traverse the freq1[] and freq2[]
for(int i = 0; i < 256; i++)
{
// If frequency of character in
// str1 is greater than str2
if (freq1[i] > freq2[i])
{
freq1[i] = freq1[i] - freq2[i];
freq2[i] = 0;
}
// Otherwise
else
{
freq2[i] = freq2[i] - freq1[i];
freq1[i] = 0;
}
}
// Store sum of freq1[]
int sum1 = 0;
// Store sum of freq2[]
int sum2 = 0;
for(int i = 0; i < 256; i++)
{
sum1 += freq1[i];
sum2 += freq2[i];
}
return Math.Max(sum1, sum2);
}
// Driver Code
public static void Main()
{
string str1 = "geeksforgeeks";
string str2 = "geeksforcoder";
Console.WriteLine(ctMinEdits(str1, str2));
}
}
// This code is contributed by code_hunt
输出：
4
时间复杂度：O(n)。
辅助空间：O(1)。
版权属于：月萌API www.moonapi.com，转载请注明出处
