Ajoutez la sous-séquence minimale requise pour ajouter la chaîne A afin d'obtenir la chaîne B

Dans ce problème, nous devons construire str2 en utilisant la sous-séquence de str1. Pour résoudre ce problème, nous pouvons trouver la sous-séquence de str1 telle qu'elle couvre la sous-chaîne avec la longueur maximale de str2. Ici, nous allons apprendre deux manières différentes de résoudre le problème.

Énoncé du problème– On nous donne deux cordes de longueurs différentes : str1 et str2. Nous devons construire str2 à partir de str1 selon les conditions suivantes.

• Choisissez n'importe quelle sous-séquence de str1 et ajoutez-la à une nouvelle chaîne (initialement vide).

Nous devons renvoyer le nombre minimum d'opérandes requis pour construire str2, ou imprimer -1 si str2 ne peut pas être construit.

Exemple

Entrez – str1 = « acd », str2 = « adc »

Sortie– 2

Instructions

La première sous-séquence de

• str1 est "ad". Ainsi, notre chaîne pourrait être « ad ».

• Ensuite, nous pouvons obtenir la sous-séquence "c" de str1 et l'ajouter à "ad" pour en faire "adc".

Entrée– str1 = "adcb", str2 = "abdca"

Sortie–3

Instructions

• La première sous-séquence est "ab" dans str1.

• Après cela, nous pouvons obtenir la chaîne "dc" et la chaîne résultante sera "abdc"

• Ensuite, nous pouvons utiliser la sous-séquence "a" pour générer la chaîne finale "abdca".

Méthode 1

Dans cette méthode, nous allons parcourir str1 pour trouver plusieurs sous-séquences et les ajouter à la chaîne résultante.

Algorithme

• Définissez le tableau "arr" de longueur 26 et initialisez tous les éléments à 0 pour stocker la présence de caractères dans str1.

• Itérer str1 et mettre à jour la valeur de l'élément du tableau en fonction de la valeur ASCII du caractère

• Définissez la variable "dernière" et initialisez-la avec -1 pour garder une trace du dernier élément visité. De plus, définissez la variable "cnt" et initialisez-la à 0 pour stocker le nombre d'opérations.

• Commencez à utiliser une boucle pour parcourir str2.

• Si le caractère actuel n'est pas dans str1, renvoie -1.

• Initialisez la variable "j" avec la valeur "last + 1".

• Utilisez une boucle while pour itérer jusqu'à ce que la valeur de j soit inférieure à len et que str1[j] ne soit pas égal au caractère

• Si la valeur de « j » est supérieure à « len », nous parcourons « str1 ». Augmentez la valeur de la variable 'cnt', initialisez 'last' à -1 car nous devons parcourir à nouveau 'str1', diminuez la valeur de 'I' de 1 car nous devons à nouveau considérer le caractère actuel, continuez à utiliser le Itération du mot-clé 'continue'.

• Mettez à jour la valeur de la variable "dernière" en "j".

• Retournez "cnt + 1" une fois toutes les itérations de la boucle terminées. Ici, nous devons ajouter « 1 » à « cnt » car nous ne considérons pas la dernière opération.

Exemple

#include <iostream>
using namespace std;

// function to count the minimum number of operations required to get string str2 from subsequences of string str1.
int minOperations(string str1, string str2){
   int len = str1.length();
   // creating an array of size 26 to store the presence of characters in string str1.
   int arr[26] = {0};
   // storing the presence of characters in string str1.
   for (int i = 0; i < len; i++){
      arr[str1[i] - 'a']++;
   }
   // store the last iterated index of string str1.
   int last = -1;
   //  to store the count of operations.
   int cnt = 0;
   for (int i = 0; i < str2.length(); i++){
      char ch = str2[i];
      // if the character is not present in string str1, then return -1.
      if (arr[ch - 'a'] == 0){
         return -1;
      }
      // start iterating from the jth index of string str1 to find the character ch.
      int j = last + 1;
      while (j < len && str1[j] != ch){
          j++;
      }
      // if j is equal to the length of string str1, then increment the count, set last to -1, and decrement i.
      if (j >= len){
         cnt++;
         last = -1;
         --i;
         continue;
      }
      // set last to j.
      last = j;
   }
   // return cnt + 1 as we haven't counted the last operation.
   return cnt + 1;
}
int main(){
   string str1 = "acd", str2 = "adc";
   int operations = minOperations(str1, str2);
   cout << "Minimum number of operations required to create string B from the subsequences of the string A is: " << operations << "\n";
   return 0;
}

Sortie

Minimum number of operations required to create string B from the subsequences of the string A is: 2

Complexité temporelle – O(N*M), où N est la longueur de str2 et M est la longueur de str1.

Complexité spatiale - O(1) puisque nous n'utilisons aucun espace dynamique.

Méthode 2

Dans cette méthode, nous utiliserons des structures de données de cartographie et de collecte pour améliorer l'efficacité de la méthode ci-dessus. La logique pour résoudre le problème est la même que ci-dessus.

Algorithme

• Définissez "chars_mp" pour stocker char -> sets{} sous forme de paires clé-valeur.

• Dans la carte, stockez l'ensemble des indices où des caractères spécifiques existent dans la chaîne str1

• Définissez les variables «dernier» et «cnt»

• Commencez à parcourir str2. Si la taille de la collection contenant l'index de caractères actuel est nulle, -1 est renvoyé.

• Trouvez la limite supérieure de "dernier" dans le jeu d'index de caractères actuel.

• Si la limite supérieure n'est pas trouvée, augmentez la valeur de "cnt" de 1, définissez "last" sur -1, diminuez la valeur de "I" de 1 et utilisez le mot-clé continue.

• Mettez à jour la valeur de la variable "dernière".

• Une fois l'itération de la boucle terminée, renvoyez la valeur de la variable 'cnt'

Exemple

#include <iostream>
#include <map> 
#include <set>
using namespace std;

// function to count the minimum number of operations required to get string str2 from subsequences of string str1.
int minOperations(string str1, string str2){
   // Length of string str1
   int len = str1.length();
   // creating the map to store the set of indices for each character in str1
   map<char, set<int>> chars_mp;
   // Iterate over the characters of str1 and store the indices of each character in the map
   for (int i = 0; i < len; i++){
      chars_mp[str1[i]].insert(i);
   }
   // store the last visited index of str1
   int last = -1;
   // Stores the required count
   int cnt = 1;
   // Iterate over the characters of str2
   for (int i = 0; i < str2.length(); i++){
      char ch = str2[i];
      // If the set of indices of str2[i] is empty, then return -1
      if (chars_mp[ch].size() == 0){
         return -1;
      }
      // If the set of indices of str2[i] is not empty, then find the upper bound of last in the set of indices of str2[i]
      // It finds the smallest index of str2[i] which is greater than last
      auto it = chars_mp[ch].upper_bound(last);
      // If the upper bound is equal to the end of the set, then increment the count and update last to -1
       if (it == chars_mp[ch].end()){
          last = -1;
          cnt++;
          // Decrement I by 1 to process the current character again
          --i;
          continue;
      }
      // Update last to the current index
      last = *it;
   }
   return cnt;
}
int main(){
   string str1 = "adcb", str2 = "abdca";
   int operations = minOperations(str1, str2);
   cout << "Minimum number of operations required to create string B from the subsequences of the string A is: " << operations << "\n";
   return 0;
}

Sortie

Minimum number of operations required to create string B from the subsequences of the string A is: 3

Complexité temporelle – O(N*logN), puisque nous parcourons str2 et trouvons la limite supérieure du « dernier » index de la boucle.

Complexité spatiale – O(N) car nous utilisons une carte pour stocker les indices de caractères.

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!