Minimiser le nombre d'opérations requises de telle sorte que deux chaînes données soient des permutations l'une de l'autre

Dans cet article, nous verrons comment minimiser le nombre d'opérations données nécessaires pour aligner deux chaînes données l'une avec l'autre. Nous suivrons l’approche étape par étape et fournirons une implémentation en code C++. Nous fournirons également un exemple de cas de test pour vous aider à comprendre le problème et la solution.

Énoncé du problème

Étant donné deux chaînes s1 et s2, nous devons trouver le nombre minimum d'opérations requises pour aligner s1 et s2 l'un avec l'autre. Nous pouvons effectuer deux opérations : échanger deux caractères de s1 ou échanger deux caractères de s2.

Méthodologie et mise en œuvre

Pour résoudre ce problème, nous devons compter le nombre de caractères qui n'existent pas dans les deux chaînes, c'est-à-dire la différence de fréquence d'apparition des caractères dans les deux chaînes. Le nombre minimum d'échanges requis pour aligner deux chaînes l'une sur l'autre est égal à la moitié de ce nombre, puisque nous pouvons échanger les caractères de l'une ou l'autre chaîne pour les rendre égaux.

Tout d’abord, nous utiliserons deux tableaux pour calculer la fréquence des caractères dans deux chaînes. Nous allons ensuite parcourir les deux tableaux et ajouter la différence absolue entre les fréquences des caractères à une variable. Cette variable stockera le nombre de caractères qui ne sont pas présents dans les deux chaînes.

Après avoir calculé le décompte, nous en renvoyons la moitié comme nombre minimum d'échanges requis pour que les deux chaînes soient permutées l'une avec l'autre.

Exemple

Ce qui suit est l'implémentation du code C++ de la méthode ci-dessus -

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

int countMinSwaps(string s1, string s2) {
   int freq1[26] = {0}, freq2[26] = {0}, count = 0;
   for (char c : s1) {
      freq1[c - 'a']++;
   }
   for (char c : s2) {
      freq2[c - 'a']++;
   }
   for (int i = 0; i < 26; i++) {
      count += abs(freq1[i] - freq2[i]);
   }
   return count / 2;
}

int main() {
   string s1 = "hello";
   string s2 = "world";
   int minSwaps = countMinSwaps(s1, s2);
   cout << "Minimum number of swaps required: " << minSwaps << endl;
   return 0;
}

Sortie

Minimum number of swaps required: 3

Exemples de cas de test

Considérons les exemples de chaînes "hello" et "world" pour ce cas de test.

Les tableaux de fréquences de deux chaînes sont les suivants -

freq1 = {0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 2, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
freq2 = {0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 2, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0}

On voit que le caractère "l" apparaît avec la fréquence 2 dans s1 mais seulement 1 dans s2, tandis que le caractère "r" apparaît avec la fréquence 1 dans s2 mais est absent dans s1. Par conséquent, le nombre de caractères qui ne sont pas présents dans les deux chaînes est de 3.

Par conséquent, le nombre minimum d'échanges requis pour que deux chaînes soient permutées l'une avec l'autre est de 1. Nous pouvons échanger le "l" de s1 avec le "r" de s2 pour obtenir les chaînes "herlo" et "wolld", qui sont des permutations l'une de l'autre.

Conclusion

Dans cet article, nous avons expliqué comment minimiser le nombre d'opérations données nécessaires pour aligner deux chaînes données l'une avec l'autre. Nous avons suivi une approche étape par étape et fourni l'implémentation du code C++. Nous fournissons également un exemple de cas de test pour vous aider à comprendre le problème et la solution. Le problème peut être résolu en complexité temporelle O(n) et en complexité spatiale O(1).

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!