Comptez le nombre de paires de chaînes qui diffèrent sur une seule position

Présentation

Les chaînes sont constituées de caractères alphanumériques dont chacun est associé à une position déterminée. Les positions des caractères vont de 0 à la longueur de la chaîne. Les caractères complètement différents dans une position sont appelés caractères adjacents.

Dans cet article, nous allons développer un code qui prend en entrée un tableau de chaînes complètement différentes à une position. Voyons l'exemple ci-dessous pour mieux comprendre ce sujet -

Exemple

Exemple 1 - str - {"abc", "cba", "dbc", "acc"}

Sortie - 2

Par exemple, dans l'exemple ci-dessous, deux paires {"abc", "dbc"} et {"abc", acc"} peuvent être générées. Ces chaînes ne diffèrent que par une seule position de caractère chacune.

Dans cet article, nous développerons un code qui utilise le mappage pour stocker des chaînes similaires et un modèle pour obtenir le nombre total de paires de chaînes. Les cartes C++ utilisent des paires clé-valeur afin de stocker et de récupérer des données avec une complexité temporelle constante.

Grammaire

substr()

La méthode

substr() est utilisée pour accéder à la sous-chaîne du début à la fin-1 dans une chaîne plus grande. Tous les index accessibles doivent être contigus et ordonnés.

Paramètres -

er - position de départ

end - la position finale à laquelle l'accès à la sous-chaîne se termine

Algorithme

• Accepte le vecteur de chaîne, la chaîne

• Maintenez initialement un compteur pour stocker le nombre total de paires qui satisfont à la condition.

• Maintenez deux cartes pour stocker des chaînes identiques ainsi que des chaînes qui satisfont à un modèle qui préserve les caractères génériques. Supposons que cette application soit m1.

• Maintenez une autre carte pour stocker des chaînes similaires. Supposons que cette application soit m2.

• Effectuez une itération sur le tableau d'entrée.

• Chaque fois qu'un type similaire de chaîne est observé, son décompte correspondant dans la carte m2 sera incrémenté

• Les sous-chaînes sont créées en remplaçant les caractères individuels d'une chaîne à l'aide de caractères génériques

• Chaque fois qu'un type de motif similaire est observé, le décompte correspondant dans le tracé m1 est incrémenté

• Calculez la somme des paires de cordes observées respectivement en m1 et m2.

• Utilisez ces valeurs additionnées pour augmenter le décompte.

Exemple

L'extrait de code C++ suivant est utilisé pour prendre un tableau de chaînes en entrée et compter le nombre total de paires qui diffèrent par une seule position -

//including the required libraries
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of same pairs
int countPairs(map<string, int> &d) {
   //maintaining the count 
   int sum = 0;
   for (auto i : d)
       sum += (i.second * (i.second - 1)) / 2;
 
   return sum;
}
//called method to calculate strings differing by one character
void chardiff(vector<string> &array, int len , int n ) {
   //count to store pairs
    int cnt = 0;
   //storing strings with wildcard characters
    map<string, int> pattern;
   //storing equivalent strings
    map<string, int> similar;
   //iterating over the array
   for (auto str : array) {
      //if two strings are same , increment the count
       similar[str]+= 1;
 
      // Iterating on a single string
       for (int i = 0; i < len ; i++) {
      // Adding special symbol to the string
       string first = str.substr(0, i);
       string second = str.substr(i + 1);
       string temp =  first + "//" + second ;
 
      //incrementing if similar pattern 
        pattern[temp]+=1;
      }
   }
 
   // Return counted pairs - equal pairs
   int chnged = countPairs(pattern);
   int sim = countPairs(similar);
   cnt =  chnged - sim * len;
   cout << "The count of pairs satisfying the condition are : " << cnt; 
}
 
//calling the main method
int main() {
   int n = 4, len = 3;
   //getting a vector of strings to process
   vector<string> strings = {"get","set","bet","bat"};
   cout << "Vector of strings : " << "\n" ;
   for(auto s : strings){
       cout << s <<"\n";
   }
   //one character different
   chardiff(strings, len , n );
 
   return 0;
}

Sortie

Vector of strings − 
get
set
bet
bat
The count of pairs satisfying the condition are − 4

Conclusion

Maps simule le processus d'insertion et de mise à jour d'enregistrements avec une complexité temporelle O(1). La méthode substring en C++ peut être utilisée pour accéder aux caractères d'une chaîne dans l'ordre entre les indices spécifiés. Le produit de n et n-1 divisé par 2 donne la somme de n'importe quel nombre de paires.

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!