Compte le nombre de nouvelles paires de chaînes obtenues en échangeant les premiers caractères des paires de chaînes dans le tableau donné

Dans ce problème, nous devons sélectionner une paire de chaînes et échanger leurs premiers caractères. Après cela, nous devons calculer le nombre total de nouvelles paires. Nous pouvons résoudre ce problème en échangeant le premier caractère de chaque paire et en vérifiant s'il existe dans le tableau.

Un moyen efficace de résoudre ce problème consiste à utiliser une structure de données de carte de hachage.

Énoncé du problème - Nous avons un tableau contenant N chaînes. Nous pouvons sélectionner deux chaînes parmi tous les éléments du tableau et échanger les premiers caractères de ces deux chaînes. Nous devons compter le nombre total de nouvelles paires de chaînes générées qui ne sont pas présentes dans le tableau.

Exemple Exemple

Entrée – array[] = {"devrait", "serait", "peut"};

Sortie – 3

Explication – La paire nouvellement générée peut être pourrait et wan. Une autre paire pourrait être qui et devrait. La troisième paire pourrait être san et chould.

Entrée – array[] = {"demo", "test"};

Sortie – 1

Explication – La paire nouvellement générée qui n'existe pas dans le tableau est temo et dest.

Méthode 1

Dans cette méthode, nous utiliserons deux boucles imbriquées pour obtenir toutes les paires d'éléments du tableau. Après cela, nous échangerons les premiers caractères des deux paires. Ensuite, nous utiliserons une troisième boucle imbriquée pour vérifier si le tableau contient la paire.

Algorithme

• Définissez la variable "cnt" et initialisez-la à 0 pour stocker le nombre total de paires.

• Utilisez deux boucles imbriquées pour parcourir le tableau de chaînes et obtenir chaque paire d'éléments du tableau.

• Obtenez la paire actuelle de deux cordes.

• Si les premiers caractères de deux chaînes ne sont pas égaux, échangez-les

• Définissez les variables "isFirst" et "isSecond" et initialisez-les avec false pour savoir si la chaîne nouvellement générée est présente dans le tableau.

• Utilisez une troisième boucle imbriquée pour vérifier s'il y a une chaîne nouvellement générée dans le tableau. De plus, les valeurs des variables isFirst et isSecond sont mises à jour en fonction des chaînes du tableau.

• S'il n'y a ni la première chaîne ni la deuxième chaîne dans le tableau, augmentez la valeur de 'cnt' de 1.

• Renvoie la valeur de la variable 'cnt'.

Exemple

#include <iostream>
using namespace std;
// function to find the count of pairs of strings that can be formed by swapping the first character of the strings
int newStringPairs(string array[], int len){
   // Stores the count of pairs
   int cnt = 0;
   // Get all the pairs of strings
   for (int i = 0; i < len; i++){
      for (int j = i + 1; j < len; j++){
         // store single pair of strings
         string first = array[i], second = array[j];
         // If both strings' first characters are not equal, swap them.
         if (first[0] != second[0]){
            swap(first[0], second[0]);
            bool isFirst = false;
            bool isSecond = false;
            // Check whether the strings are present in the array or not
            for (int k = 0; k < len; k++){
               if (array[k] == first){
                  isFirst = true;
               }
                  if (array[k] == second){
                     isSecond = true;
                  }
              }
               // If both the strings are present in the array, then increment the cnt by 1
                if (isFirst == false && isSecond == false){
                    cnt++;
              }
          }
       }
    }
    return cnt;
}
int main(){
   string array[] = {"should", "would", "can"};
   int N = sizeof(array) / sizeof(array[0]);
   cout << "Total number of new pairs we can generate by swapping the first characters of given strings is " << newStringPairs(array, N);
   return 0;
}

Sortie

Total number of new pairs we can generate by swapping the first characters of given strings is 3

Complexité temporelle - O(N^3) car nous utilisons trois boucles imbriquées.

Complexité spatiale – O(1)

Méthode 2

Dans cette méthode, nous utiliserons la structure de données cartographiques pour stocker toutes les valeurs du tableau dans la carte. Ensuite, nous pouvons vérifier si la carte contient la chaîne nouvellement générée. Sinon, nous pouvons augmenter le décompte de 1.

Algorithme

• Définir la variable 'cnt'

• Parcourez le tableau de chaînes et stockez toutes les valeurs du tableau dans la carte.

• Utilisez deux boucles imbriquées pour obtenir toutes les paires d'éléments du tableau.

• Obtenez des paires de chaînes et stockez-les dans les variables "première" et "seconde".

• Si les premiers caractères de deux chaînes ne sont pas égaux, échangez-les.

• Dans la carte, vérifiez si la chaîne nouvellement générée est incluse. Sinon, augmentez la valeur de "cnt" de 1.

• Renvoyer la valeur « cnt ».

Exemple

#include <iostream>
#include <unordered_map>
using namespace std;

// function to find the count of pairs of strings that can be formed by swapping the first character of the strings
int newStringPairs(string array[], int len){
    // to store the total number of new pairs
    int cnt = 0;
    // add all strings to the array map
    unordered_map<string, int> str_map;
    for (int i = 0; i < len; i++){
       str_map[array[i]]++;
    }
    //find all pairs of strings that can be formed by swapping the first character of the strings
    for (int i = 0; i < len; i++){
       for (int j = i + 1; j < len; j++){
          // get the current pair of strings
          string first = array[i];
          string second = array[j];
          // If the first character of both strings is not the same, then swap them
          if (first[0] != second[0]){
             swap(first[0], second[0]);
             // If both strings are not present in the map, then the increment count
             if (str_map[first] == 0 && str_map[second] == 0){
                cnt++;
               }
            }
         }
      }
   return cnt;
}
int main(){
   string array[] = {"should", "would", "can"};
   int N = sizeof(array) / sizeof(array[0]);
   cout << "Total number of new pairs we can generate by swapping the first characters of given strings is " << newStringPairs(array, N);
   return 0;
}

Sortie

Total number of new pairs we can generate by swapping the first characters of given strings is 3

Complexité temporelle - O(N^2) car nous utilisons deux boucles imbriquées.

Complexité spatiale – O(N) car nous utilisons une carte pour stocker tous les éléments du tableau.

Nous connaissons le nombre total de paires nouvellement générées en échangeant les premiers caractères de tous les éléments du tableau. Nous avons optimisé le code de la deuxième méthode en termes de complexité temporelle, mais le code de la première méthode est meilleur en termes de complexité spatiale.

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!