Ermitteln Sie anhand eines gegebenen Arrays die maximale Summe der Längen zweier Zeichenfolgen, die nicht dieselben Zeichen enthalten.

Der Zweck dieses Artikels besteht darin, ein Programm zu implementieren, um die Summe der Längen eines Zeichenfolgenpaars ohne gemeinsame Zeichen in einem bestimmten Array zu maximieren. Per Definition ist eine Zeichenfolge eine Ansammlung von Zeichen.

Problemstellung

Implementieren Sie ein Programm, um die Summe der Längen eines Zeichenfolgenpaars ohne gemeinsame Zeichen in einem bestimmten Array zu maximieren.

Beispiel 1

Let us consider the Input array: 
a[] = [“efgh”, “hat”, “fto”, “car”, “wxyz”, “fan”]

Output obtained: 8

Anleitung

In den Zeichenfolgen „abcd“ und „wxyz“ gibt es keine gemeinsamen Zeichen. Infolgedessen beträgt die kombinierte Länge der beiden Zeichenfolgen 4 + 4, was 8 entspricht, der längsten Länge unter allen möglichen Paaren.

Beispiel 2

Let us consider the Input array: 
a[] = [“abc”, “cat”, “bat”, “hij”, “abcd”, “an”, "can"]

Output obtained: 7

Anleitung

In den Zeichenfolgen „abcd“ und „hij“ gibt es keine gemeinsamen Zeichen. Infolgedessen beträgt die kombinierte Länge der beiden Zeichenfolgen 4 + 3, was 8 entspricht, der längsten Länge unter allen möglichen Paaren.

Beispiel 3

Let us consider the Input array: 
a[] = [“xyz”, “zip”, “lmno”, “lot”, “abcdx”, “yo”]

Output obtained: 9

Anleitung

In den Zeichenfolgen „abcdx“ und „lmno“ gibt es keine gemeinsamen Zeichen. Infolgedessen beträgt die kombinierte Länge der beiden Zeichenfolgen 5 + 4, was 9 entspricht und die längste Länge aller möglichen Paare ist.

Beispiel 4

Let us consider the Input array: 
a[] = [“abc”, “coat”, “bat”, “hij”, “abcd”, “an”]

Output obtained: 7

Anleitung

In den Zeichenfolgen „coat“ und „hij“ gibt es keine gemeinsamen Zeichen. Infolgedessen beträgt die kombinierte Länge der beiden Zeichenfolgen 4 + 3, was 8 entspricht, der längsten Länge unter allen möglichen Paaren.

Lösung

Um die Summe der Längen eines Zeichenfolgenpaars ohne gemeinsame Zeichen in einem bestimmten Array zu maximieren, verwenden wir den folgenden Ansatz.

Eine Möglichkeit, dieses Problem zu lösen oder einen Weg zu finden, die Summe der Längen eines Zeichenfolgenpaars ohne gemeinsame Zeichen im angegebenen Array zu maximieren, ist wie folgt. Der einfachste Weg, das obige Problem zu lösen, besteht jedoch darin, jedes potenzielle Paar von String-Arrays zu erstellen und dann die maximale Summe der String-Längen aller möglichen Paare ohne gemeinsame Zeichen anzuzeigen. < /p>

Mit dem Konzept der Bitoperation kann die obige Strategie auch verbessert werden. Das Ziel hier besteht darin, jede Zeichenfolge in ihre entsprechende bitmaskierte Ganzzahl umzuwandeln, bevor Zeichenfolgenpaare identifiziert werden, die keine gemeinsamen Zeichen haben und die größtmögliche Längensumme aufweisen.

BitMasking ist unser aktuelles Thema. Was genau ist eine Bitmaske?

Wir müssen uns zunächst daran erinnern, was eine ganze Zahl ist. Ganzzahlen sind nur Ansammlungen aneinandergereihter Bits. Das Konzept der Bitmaskierung besteht darin, Zahlen grafisch in binärer Form darzustellen.

Einfach ausgedrückt ist eine „Bitmaske“ eine Binärzahl, die alles spezifizieren kann.

Algorithmus

Nachfolgend finden Sie den Algorithmus zur Implementierung eines Programms zur Maximierung der Summe der Längen eines Zeichenfolgenpaars, das in einem bestimmten Array keine gemeinsamen Zeichen aufweist.

• Schritt 1 – Erste Schritte

• Schritt 2 – Erstellen Sie eine memset()-Funktion, um das Bitmasken-Array mit Nullen zu initialisieren. Eine Bitmaske der Anfangsgröße L, die zum Aufzeichnen der bitweisen ODER-Verknüpfung von Zeichenfolgen im Array strings arr[] verwendet wird.

• Schritt 3 – Um die Antwort zu speichern, setzen Sie den Wert der Variablen maxLength auf 0.

• Schritt 4 – Führen Sie Folgendes aus, während Sie mit der Variablen i über den Bereich [0, L] iterieren –

• Schritt 5 – Definieren Sie den Wert von bitmask[i] als mask[i]|1(arr[i][j] - 'a') und iterieren Sie über den Bereich [0, S], wobei S a ist Saitengröße.

• Schritt 6 – Verwenden Sie die Ganzzahlvariable j, um über den Bereich [0, i] zu iterieren und setzen Sie den Wert von maxLength auf den Maximalwert von arr[i].length() + if bitmask[i] und bitmask[ j] sind bitweise Und das Ergebnis ist nicht 0, dann arr[j].length().

• Schritt 7 – Drucken Sie abschließend die erhaltenen Ergebnisse aus.

• Schritt 8 – Stopp

Beispiel: C-Programm

Dies ist eine C-Programmimplementierung des oben beschriebenen Algorithmus, um die Summe der Längen eines Zeichenfolgenpaares ohne gemeinsame Zeichen in einem bestimmten Array zu maximieren

Dies ist eine C-Programmimplementierung des oben beschriebenen Algorithmus, um die Summe der Längen eines Zeichenfolgenpaares ohne gemeinsame Zeichen in einem bestimmten Array zu maximieren

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 26
// Defining a function maxSumLength used to determine the longest combinedlength of two strings with no shared characters
int maxSumLength(char* arr[], int n){

   // Stores the bitmask of each string
   int bitmask[n];
   
   // Initialize the bitmask of each string to 0
   memset(bitmask, 0, sizeof(bitmask));
   
   // set the res to number 0
   int res = 0;
   
   // Now iterating this
   for (int i = 0; i < n; ++i) {
   
      // For every given elements 
      for (int j = 0; j < strlen(arr[i]); ++j) {
      
         // If the ith value of bitmask |= 1 then left shift that particular character - a
         bitmask[i] |= 1 << (arr[i][j] - 'a');
      }
      
      // Check for all the ith element, whether the ith and jth values of the
      // mask are not equal, if so add and also maximize those
      for (int j = 0; j < i; ++j) {
         if (!(bitmask[i] & bitmask[j])) {
            res = (res > strlen(arr[i]) + strlen(arr[j])) ? res : strlen(arr[i]) + strlen(arr[j]);
         }
      }
   }
   
   // the obtained maximum sum of the lengths of the strings obtained is returned
   return res;
}

int main(){
   char* arr[] = { "abcd", "def", "xyz" };
   int n = sizeof(arr) / sizeof(arr[0]);
   printf("%d", maxSumLength(arr, n));
   return 0;
}

Ausgabe

7

Fazit

Ähnlich können wir die Summe der Längen eines Zeichenfolgenpaars maximieren, das im gegebenen Array keine gemeinsamen Zeichen hat.

Dieser Artikel befasst sich mit der Herausforderung, ein Programm zu erhalten, das die Summe der Längen eines Zeichenfolgenpaars maximiert, das in einem bestimmten Array keine gemeinsamen Zeichen aufweist.

C-Programmiercode wird hier zusammen mit einem Algorithmus bereitgestellt, um die Summe der Längen eines Zeichenfolgenpaars zu maximieren, das in einem bestimmten Array keine gemeinsamen Zeichen hat.

Das obige ist der detaillierte Inhalt vonErmitteln Sie anhand eines gegebenen Arrays die maximale Summe der Längen zweier Zeichenfolgen, die nicht dieselben Zeichen enthalten.. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!