Modifie une chaîne en remplaçant toutes les occurrences d'un caractère donné par un caractère de remplacement spécifié

Dans ce problème, nous devons remplacer les caractères d'une chaîne donnée en fonction des caractères donnés dans le tableau de paires de caractères. Nous discuterons de deux solutions différentes. Dans la première méthode, nous remplaçons chaque caractère en parcourant les caractères et les paires de caractères de la chaîne donnée.

Dans la deuxième méthode, nous utiliserons un tableau de longueur 26 pour stocker les caractères de remplacement associés à chaque caractère et modifier les caractères de la chaîne donnée.

Énoncé du problème - On nous donne une chaîne str contenant N caractères alphabétiques minuscules. De plus, nous recevons un tableau contenant des paires de caractères. Nous devons remplacer les caractères pairs[i][0] dans la chaîne donnée par pairs[i][1].

Exemple Exemple

Input –  str = "xyz", pairs = {{'x', 'a'}, {'y', 'b'},, {'z', 'c'}}

Output – ‘abc’

Instructions

Ici, « x » est remplacé par « a », « y » est remplacé par « b » et « z » est remplacé par « c ».

Input – str = "abderb", pairs = {{'a', 'e'}, {'b', 't'}, {'e', 'f'}, {'r', 's'}}

Output – ‘etdfst’

Instructions

Dans une chaîne, 'a' est remplacé par 'e', ​​'b' est remplacé par 't', 'e' est remplacé par 'f' et 'r' est remplacé par 's'.

Méthode 1

Dans cette méthode, nous allons parcourir chaque paire de caractères et remplacer les caractères correspondants dans la chaîne donnée. Nous avons besoin de deux boucles imbriquées pour parcourir la chaîne pour chaque boucle.

Algorithme

• Étape 1 - Stockez la taille de la chaîne dans la variable 'N' et le tableau dans la variable 'M'.

• Étape 2 - Stockez une copie de la chaîne dans la variable 'temp'.

• Étape 3 - Utilisez une boucle for pour parcourir la liste des paires.

• Étape 4 - Dans la boucle, stockez le premier caractère dans la variable « a » et le deuxième caractère dans la variable « b ».

• Étape 5 - Parcourez la chaîne en utilisant des boucles imbriquées.

• Étape 6 - Dans la boucle imbriquée, si le caractère actuel de la chaîne donnée est égal à 'a', remplacez le caractère actuel par 'b' dans la chaîne temporaire.

• Étape 7 - Renvoyez la valeur de temp.

Exemple

#include <bits/stdc++.h>
using namespace std;
string replaceChars(string str, vector<vector<char>> pairs){
   // stror the size of the string and the array
   int N = str.size(), M = pairs.size();
   
   // Create a copy of the string str
   string temp = str;
   
   // Iterate over the array
   for (int x = 0; x < M; x++){
   
      // store the characters from the pair
      char a = pairs[x][0], b = pairs[x][1];
      
      // iterate over the string
      for (int y = 0; y < N; y++){
      
         // If the character is equal to a, then replace it with b
         if (str[y] == a){
            temp[y] = b;
         }
      }
   }
   return temp;
}
int main(){
   string str = "abderb";
   vector<vector<char>> pairs{{'a', 'e'},
      {'b', 't'},
      {'e', 'f'},
      {'r', 's'}};
   cout << "The string after replacing with the given characters is - " << replaceChars(str, pairs);
   return 0;
}

Sortie

The string after replacing with the given characters is - etdfst	

Complexité temporelle - O(N*M), où N est la longueur de la chaîne et M est la longueur du tableau de paires de caractères.

Complexité spatiale - O(N) car nous stockons la nouvelle chaîne dans la variable temp.

Méthode 2

Dans cette méthode, nous pouvons créer un tableau de taille 26. Nous pouvons alors stocker le caractère remplaçable à la position actuelle du caractère. Enfin, nous pouvons prendre les éléments remplaçables du tableau et mettre à jour chaque caractère de la chaîne.

Algorithme

• Étape 1 - Obtenez la taille de la chaîne comme « N » et la taille du tableau comme « M ».

• Étape 2 - Définissez les tableaux "initial" et "final" de longueur 26.

• Étape 3 - Parcourez la chaîne et stockez str[Y] dans l'index initial et final du tableau de "str[Y] - a". Ici, str[Y] - 'a' donne un index compris entre 0 et 25 basé sur la valeur ASCII du caractère.

La raison pour laquelle str[Y] est stocké à la position 'str[Y] - a' dans le tableau initial et final est que si un caractère est présent dans la chaîne mais pas dans la paire de caractères, nous pouvons le conserver dans la chaîne finale constante. .

• Étape 4 - Parcourez le tableau donné de paires de caractères. Dans la boucle, utilisez des boucles imbriquées pour parcourir le tableau initial. Si le premier caractère de la paire courante est égal au caractère du tableau "initial", les caractères du tableau "final" sont mis à jour avec le deuxième caractère de la paire courante.

• Étape 5 - Définissez la variable 'result' et initialisez-la avec une chaîne vide.

• Étape 6 - Parcourez la chaîne d'entrée, récupérez le caractère correspondant du caractère actuel à partir du tableau "final" et ajoutez-le à la chaîne "résultat".

• Étape 7 - Renvoyez la chaîne « résultat ».

Exemple

#include <bits/stdc++.h>
using namespace std;
//  Function to replace the characters in the string
string replaceChars(string str, vector<vector<char>> pairs){

   // getting the size of the string and the vector
   int N = str.size(), M = pairs.size();
   
   // Declare two arrays of size 26
   char initial[26];
   char final[26];
   
   // Check all existing characters in the string
   for (int Y = 0; Y < N; Y++){
      initial[str[Y] - 'a'] = str[Y]; final[str[Y] - 'a'] = str[Y];
   }
   
   // Iterate over the range [0, M]
   for (int X = 0; X < M; X++){
   
      // get characters from the vector
      char a = pairs[X][0], b = pairs[X][1];
      
      // Iterate over the range [0, 26]
      for (int Y = 0; Y < 26; Y++){
      
         // If the character is the same as a, then replace it with b in the final array
         if (initial[Y] == a){
            final[Y] = b;
         }
      }
   }
   string result = "";
   
   // get the final string using the final array
   for (int Y = 0; Y < N; Y++){
      result += final[str[Y] - 'a'];
   }
   return result;
}
int main(){
   string str = "aberb";
   vector<vector<char>> pairs{{'a', 'e'},
      {'b', 't'},
      {'e', 'f'},
      {'r', 's'}};
   cout << "The string after replacing with the given characters is - " << replaceChars(str, pairs);
   return 0;
}

Sortie

The string after replacing with the given characters is - etfst

Complexité temporelle - O(N), comme boucle imbriquée, itération constante uniquement.

Complexité spatiale - O(1), car il utilise un tableau de longueur 26, qui est constante.

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!