Zählt die Anzahl neuer Zeichenfolgenpaare, die durch Vertauschen der ersten Zeichen von Zeichenfolgenpaaren im angegebenen Array erhalten werden

In diesem Problem müssen wir ein Paar Zeichenfolgen auswählen und ihre ersten Zeichen austauschen. Danach müssen wir die Gesamtzahl der neuen Paare berechnen. Wir können dieses Problem lösen, indem wir das erste Zeichen jedes Paars vertauschen und prüfen, ob es im Array vorhanden ist.

Eine effiziente Möglichkeit, dieses Problem zu lösen, ist die Verwendung einer Hash-Map-Datenstruktur.

Problemstellung – Wir haben ein Array mit N Zeichenfolgen. Wir können aus allen Array-Elementen zwei beliebige Strings auswählen und die ersten Zeichen dieser beiden Strings vertauschen. Wir müssen die Gesamtzahl der neu generierten Zeichenfolgenpaare zählen, die nicht im Array vorhanden sind.

Beispiel Beispiel

Eingabe – array[] = {"should", "would", "can"};

Ausgabe – 3

Erklärung – Das neu generierte Paar kann sein und sein. Ein anderes Paar könnte sein, wer und sollte. Das dritte Paar könnten San und Chould sein.

Eingabe – array[] = {"demo", "test"};

Ausgabe – 1

Erklärung – Das neu generierte Paar, das nicht im Array existiert, ist Temo und Dest.

Methode 1

Bei dieser Methode verwenden wir zwei verschachtelte Schleifen, um alle Array-Elementpaare abzurufen. Danach werden wir die ersten Zeichen der beiden Paare vertauschen. Als Nächstes verwenden wir eine dritte verschachtelte Schleife, um zu prüfen, ob das Array das Paar enthält.

Algorithmus

• Definieren Sie die Variable „cnt“ und initialisieren Sie sie auf 0, um die Gesamtzahl der Paare zu speichern.

• Verwenden Sie zwei verschachtelte Schleifen, um das String-Array zu durchlaufen und jedes Array-Elementpaar abzurufen.

• Holen Sie sich das aktuelle Paar aus zwei Saiten.

• Wenn die ersten Zeichen zweier Zeichenfolgen nicht gleich sind, tauschen Sie sie aus

• Definieren Sie die Variablen „isFirst“ und „isSecond“ und initialisieren Sie sie mit „false“, um zu verfolgen, ob die neu generierte Zeichenfolge im Array vorhanden ist.

• Verwenden Sie eine dritte verschachtelte Schleife, um zu prüfen, ob sich im Array eine neu generierte Zeichenfolge befindet. Darüber hinaus werden die Werte der Variablen isFirst und isSecond basierend auf den Zeichenfolgen im Array aktualisiert.

• Wenn weder die erste noch die zweite Zeichenfolge im Array vorhanden ist, erhöhen Sie den Wert von „cnt“ um 1.

• Gibt den Wert der Variablen „cnt“ zurück.

Beispiel

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

Ausgabe

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

Zeitkomplexität – O(N^3), weil wir drei verschachtelte Schleifen verwenden.

Raumkomplexität – O(1)

Methode 2

Bei dieser Methode verwenden wir die Kartendatenstruktur, um alle Array-Werte in der Karte zu speichern. Anschließend können wir prüfen, ob die Karte den neu generierten String enthält. Wenn nicht, können wir die Anzahl um 1 erhöhen.

Algorithmus

• Variable „cnt“ definieren

• Durchlaufen Sie das String-Array und speichern Sie alle Array-Werte in der Karte.

• Verwenden Sie zwei verschachtelte Schleifen, um alle Paare von Array-Elementen abzurufen.

• Holen Sie sich String-Paare und speichern Sie sie in den Variablen „erste“ und „zweite“.

• Wenn die ersten Zeichen zweier Zeichenfolgen nicht gleich sind, tauschen Sie sie aus.

• Überprüfen Sie in der Karte, ob die neu generierte Zeichenfolge enthalten ist. Wenn nicht, erhöhen Sie den Wert von „cnt“ um 1.

• Gibt den „cnt“-Wert zurück.

Beispiel

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

Ausgabe

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

Zeitkomplexität – O(N^2), weil wir zwei verschachtelte Schleifen verwenden.

Raumkomplexität – O(N), weil wir eine Karte verwenden, um alle Array-Elemente zu speichern.

Wir kennen die Gesamtzahl der neu generierten Paare, indem wir die ersten Zeichen aller Array-Elemente austauschen. Wir haben den Code für die zweite Methode hinsichtlich der zeitlichen Komplexität optimiert, aber der Code der ersten Methode ist hinsichtlich der räumlichen Komplexität besser.

Das obige ist der detaillierte Inhalt vonZählt die Anzahl neuer Zeichenfolgenpaare, die durch Vertauschen der ersten Zeichen von Zeichenfolgenpaaren im angegebenen Array erhalten werden. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!