Nombre minimum de swaps adjacents requis pour inverser une chaîne

Étant donné une chaîne str, nous pouvons inverser la chaîne en échangeant simplement les caractères adjacents. Nous devons trouver le nombre minimum de mouvements requis pour inverser la chaîne, simplement en échangeant les caractères adjacents. Nous mettrons en œuvre deux méthodes pour trouver la solution requise et fournirons une explication et une implémentation du code.

Exemple Exemple

Input1: string str1 = “shkej”

Output: 10

La traduction chinoise de

Explication

est :

Explication

Tout d'abord, nous allons déplacer le dernier caractère vers la première position, ce qui nécessitera 4 échanges, puis la chaîne deviendra "jshke". Ensuite, nous déplacerons le « e » vers la deuxième position, ce qui nécessitera 3 échanges. De même, pour « k », nous avons besoin de deux échanges, tandis que pour « h », un seul échange est requis et la réponse finale est 10.

Input2: string str1 = “abace”

Output: 6

La traduction chinoise de

Explication

est :

Explication

Nous allons d'abord échanger le caractère au 2ème index et le déplacer vers le dernier index, cela prendra 2 échanges et la chaîne deviendra "abcea". Ensuite on échange 'b' contre 'e', ​​​​cela prendra 2 échanges et la chaîne deviendra "aceba". Effectuez ensuite 2 échanges supplémentaires pour obtenir la chaîne inversée finale, ce qui nécessite un total de 6 échanges.

La traduction chinoise de

Approche Naive

est :

Approche Naive

Nous avons examiné l'exemple ci-dessus, examinons maintenant les étapes nécessaires pour implémenter le code correct.

• Tout d'abord, nous allons créer une fonction qui prendra la chaîne donnée comme paramètre et renverra le nombre minimum d'étapes requis comme valeur de retour.

• Dans cette fonction, nous allons créer une copie de la chaîne, puis l'inverser pour la comparer avec la chaîne d'origine.

• Nous allons créer trois variables, les deux premières seront utilisées pour parcourir la chaîne et la dernière sera utilisée pour stocker le nombre d'étapes requis.

• En utilisant une boucle while, nous allons parcourir la chaîne donnée et continuer à sauter le même nombre d'itérations que la valeur d'index actuelle pour inverser la chaîne.

• Ensuite, nous utiliserons une boucle while pour échanger les caractères adjacents jusqu'à ce que « j » atteigne « i » et incrémenterons le décompte à chaque échange.

• Enfin, nous renverrons la valeur du décompte et l'imprimerons dans la fonction principale.

Exemple

#include <bits/stdc++.h>
using namespace std;
// function to get the minimum number of swaps 
int minSwaps(string str){
   string temp = str;
   reverse(temp.begin(), temp.end()); // reversing the string 
   int i = 0, j = 0;
   int ans = 0;
   int len = str.size();
   while (i <len) {
      j = i;		
      // find the character that is equal to the current element 
      while (str[j] != temp[i]) {
         j++;
      }
      // iterating util the current i is equal to j
      while (i < j) {
         char tempc = str[j];
         str[j] = str[j - 1];
         str[j - 1] = tempc;
         j--;
         ans++;
      }
      i++;
   }
   return ans;
}
int main(){
   string str = "efabc"; // given string     
   // calling the function to find the minimum number of steps required 
   cout<<"The minimum number of steps required to reverse the given string by swapping the adjacent characters is "<<minSwaps(str)<<endl;
   return 0;
}

Sortie

The minimum number of steps required to reverse the given string by swapping the adjacent characters is 10

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(N^2), où N est la longueur de la chaîne donnée. Nous utilisons des boucles while imbriquées pour donner des facteurs de N lors de l'itération.

La complexité spatiale du code ci-dessus est O(N) car nous y créons une chaîne supplémentaire pour stocker l'inversion de la chaîne donnée.

REMARQUE - Une approche alternative est ici possible, mais nécessite l'utilisation de structures de données très avancées. Le concept de cette méthode est que nous pouvons commencer par le dernier caractère et vérifier jusqu'à ce que le premier caractère remplisse la condition. Ensuite, en théorie, nous pourrions déplacer ce caractère vers la dernière position, marquer cette position comme terminée et stocker cette valeur dans une structure de données de haut niveau.

Ensuite, pour chaque personnage, nous trouverons le même personnage venant de derrière qui n'a pas encore été tagué, puis augmenterons le nombre jusqu'au nombre total d'éléments après moins le nombre d'éléments tagués.

Conclusion

Dans ce tutoriel, nous avons implémenté un code pour trouver le nombre minimum d'étapes requises pour inverser une chaîne donnée en échangeant uniquement les caractères adjacents. Nous avons utilisé des boucles while imbriquées et inversé la copie de la chaîne donnée pour trouver la solution. La complexité temporelle du code ci-dessus est O(N^2), où N est la taille de la chaîne et la complexité spatiale est O(N).

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!