Zählen Sie die Anzahl der Saitenpaare, die sich nur an einer Position unterscheiden

Einführung

Strings bestehen aus alphanumerischen Zeichen, denen jeweils eine bestimmte Position zugeordnet ist. Die Zeichenpositionen reichen von 0 bis zur Zeichenfolgenlänge. Zeichen, die an einer Stelle völlig unterschiedlich sind, nennt man benachbarte Zeichen.

In diesem Artikel entwickeln wir einen Code, der als Eingabe ein Array von Zeichenfolgen verwendet, die an einer Position völlig unterschiedlich sind. Sehen wir uns das Beispiel unten an, um dieses Thema besser zu verstehen -

Beispiel

Beispiel 1 – str – {"abc", "cba", "dbc", "acc"}

Ausgabe – 2

Im folgenden Beispiel können beispielsweise zwei Paare {"abc", "dbc"} und {"abc", acc"} generiert werden. Diese Zeichenfolgen unterscheiden sich jeweils nur in einer Zeichenposition.

In diesem Artikel entwickeln wir einen Code, der Mapping zum Speichern ähnlicher Zeichenfolgen und ein Muster verwendet, um die Gesamtzahl der Zeichenfolgenpaare zu ermitteln. C++-Maps nutzen Schlüssel-Wert-Paare, um Daten mit konstanter Zeitkomplexität zu speichern und abzurufen.

Grammatik

substr()

Die Methode

substr() wird verwendet, um auf den Teilstring von Anfang bis Ende-1 in einem größeren String zuzugreifen. Alle Indizes, auf die zugegriffen werden soll, sollten zusammenhängend und geordnet sein.

Parameter -

st - Ausgangsposition

end – Die Endposition, an der der Teilstring-Zugriff beendet wird

Algorithmus

• Akzeptiert String-Vektor, String

• Behalten Sie zunächst einen Zähler bei, um die Anzahl der Gesamtpaare zu speichern, die die Bedingung erfüllen.

• Behalten Sie zwei Karten bei, um identische Zeichenfolgen sowie Zeichenfolgen zu speichern, die einem Muster entsprechen, das Platzhalter beibehält. Nehmen wir an, dass diese Abbildung m1 ist.

• Behalten Sie eine andere Karte bei, um ähnliche Zeichenfolgen zu speichern. Nehmen wir an, dass diese Abbildung m2 ist.

• Führen Sie eine Iteration über das Eingabearray durch.

• Jedes Mal, wenn eine ähnliche Art von Zeichenfolge beobachtet wird, wird die entsprechende Anzahl in der m2-Karte erhöht

• Teilzeichenfolgen werden erstellt, indem einzelne Zeichen einer Zeichenfolge durch Platzhalter ersetzt werden

• Jedes Mal, wenn ein ähnlicher Mustertyp beobachtet wird, wird die entsprechende Anzahl im m1-Diagramm erhöht

• Berechnen Sie die Summe der in m1 bzw. m2 beobachteten Stringpaare.

• Verwenden Sie diese summierten Werte, um die Anzahl zu erhöhen.

Beispiel

Der folgende C++-Codeausschnitt wird verwendet, um ein Array von Zeichenfolgen als Eingabe zu verwenden und die Gesamtzahl der Paare zu zählen, die sich nur an einer Position unterscheiden -

//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;
}

Ausgabe

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

Fazit

Maps simuliert den Prozess des Einfügens und Aktualisierens von Datensätzen mit einer Zeitkomplexität von O(1). Die Teilzeichenfolgenmethode in C++ kann verwendet werden, um auf die Zeichen einer Zeichenfolge in der Reihenfolge zwischen angegebenen Indizes zuzugreifen. Das Produkt aus n und n-1 dividiert durch 2 ergibt die Summe beliebig vieler Paare.

Das obige ist der detaillierte Inhalt vonZählen Sie die Anzahl der Saitenpaare, die sich nur an einer Position unterscheiden. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!