Diberi tatasusunan, cari jumlah maksimum panjang dua rentetan yang tidak mempunyai aksara yang sama.

Tujuan artikel ini adalah untuk melaksanakan program untuk memaksimumkan jumlah panjang sepasang rentetan tanpa aksara biasa dalam tatasusunan tertentu. Mengikut definisi, rentetan ialah koleksi aksara.

Pernyataan Masalah

Laksanakan atur cara untuk memaksimumkan jumlah panjang sepasang rentetan tanpa aksara biasa dalam tatasusunan tertentu.

Contoh 1

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

Output obtained: 8

Arahan

Tiada aksara biasa dalam rentetan "abcd" dan "wxyz". Akibatnya, panjang gabungan dua rentetan ialah 4 + 4, iaitu bersamaan dengan 8, panjang terpanjang antara semua pasangan yang boleh dilaksanakan.

Contoh 2

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

Output obtained: 7

Arahan

Tiada aksara biasa dalam rentetan "abcd" dan "hij". Akibatnya, panjang gabungan dua rentetan ialah 4 + 3, yang sama dengan 8, panjang terpanjang antara semua pasangan yang boleh dilaksanakan.

Contoh 3

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

Output obtained: 9

Arahan

Tiada aksara biasa dalam rentetan "abcdx" dan "lmno". Hasilnya, panjang gabungan dua rentetan ialah 5 + 4, yang sama dengan 9 dan merupakan panjang terpanjang antara semua pasangan yang boleh dilaksanakan.

Contoh 4

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

Output obtained: 7

Arahan

Tiada aksara biasa dalam rentetan "kot" dan "hij". Akibatnya, panjang gabungan dua rentetan ialah 4 + 3, yang sama dengan 8, panjang terpanjang antara semua pasangan yang boleh dilaksanakan.

Penyelesaian

Untuk memaksimumkan jumlah panjang sepasang rentetan tanpa aksara biasa dalam tatasusunan tertentu, kami menggunakan pendekatan berikut.

Satu cara untuk menyelesaikan masalah ini atau mencari cara untuk memaksimumkan jumlah panjang sepasang rentetan tanpa aksara biasa dalam tatasusunan yang diberikan adalah seperti berikut. Walau bagaimanapun, cara paling mudah untuk menangani masalah di atas ialah mencipta setiap pasangan berpotensi tatasusunan rentetan dan kemudian memaparkan jumlah maksimum panjang rentetan semua pasangan yang mungkin tanpa aksara yang sama. < /p>

Menggunakan konsep operasi bit, strategi di atas juga boleh diperbaiki. Matlamat di sini adalah untuk menukar setiap rentetan kepada integer bertopeng bit yang setara sebelum mengenal pasti pasangan rentetan yang tidak berkongsi aksara sepunya dan mempunyai jumlah panjang terpanjang yang mungkin.

BitMasking ialah tema semasa kami. Apa sebenarnya topeng sedikit?

Kita mesti ingat dahulu apa itu integer. Integer hanyalah koleksi bit yang dirangkai bersama. Konsep bit masking adalah untuk mewakili nombor secara grafik menggunakan bentuk binari.

Ringkasnya, "bitmask" ialah nombor binari yang boleh menentukan apa sahaja.

Algoritma

Diberikan di bawah ialah algoritma untuk melaksanakan program untuk memaksimumkan jumlah panjang sepasang rentetan yang tidak mempunyai aksara yang sama dalam tatasusunan tertentu.

• Langkah 1 - Mulakan

• Langkah 2 - Buat fungsi memset() untuk memulakan tatasusunan bitmask dengan sifar. Topeng bit saiz awal L digunakan untuk merekod bitwise ATAU rentetan dalam tatasusunan rentetan arr[].

• Langkah 3 - Untuk menyimpan respons, tetapkan nilai pembolehubah maxLength kepada 0.

• Langkah 4 - Lakukan perkara berikut sambil mengulangi julat [0, L] menggunakan pembolehubah i -

• Langkah 5 - Takrifkan nilai bitmask[i] sebagai mask[i]|1(arr[i][j] - 'a') dan lelaran ke atas julat [0, S], dengan S ialah a saiz tali.

• Langkah 6 - Gunakan pembolehubah integer j untuk lelaran pada julat [0, i] dan tetapkan nilai maxLength kepada nilai maksimum arr[i].length() + jika bitmask[i] dan bitmask[ j] adalah bitwise Jika hasilnya bukan 0, maka arr[j].length().

• Langkah 7 - Akhirnya cetak keputusan yang diperolehi.

• Langkah 8 - Berhenti

Contoh: program C

Ini ialah pelaksanaan program C bagi algoritma yang ditulis di atas untuk memaksimumkan jumlah panjang sepasang rentetan tanpa aksara yang sama dalam tatasusunan yang diberikan

Ini ialah pelaksanaan program C bagi algoritma yang ditulis di atas untuk memaksimumkan jumlah panjang sepasang rentetan tanpa aksara yang sama dalam tatasusunan yang diberikan

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

Output

7

Kesimpulan

Begitu juga, kita boleh memaksimumkan jumlah panjang sepasang rentetan yang tidak mempunyai aksara sepunya dalam tatasusunan yang diberikan.

Artikel ini menangani cabaran mendapatkan atur cara untuk memaksimumkan jumlah panjang sepasang rentetan yang tidak mempunyai aksara yang sama dalam tatasusunan tertentu.

Kod pengaturcaraan C disediakan di sini bersama-sama dengan algoritma untuk memaksimumkan jumlah panjang sepasang rentetan yang tidak mempunyai aksara biasa dalam tatasusunan tertentu.

Atas ialah kandungan terperinci Diberi tatasusunan, cari jumlah maksimum panjang dua rentetan yang tidak mempunyai aksara yang sama.. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!