Mengira bilangan pasangan rentetan baharu yang diperoleh dengan menukar aksara pertama pasangan rentetan dalam tatasusunan yang diberikan

Dalam masalah ini, kita perlu memilih sepasang rentetan dan menukar aksara pertama mereka. Selepas itu, kita perlu mengira jumlah bilangan pasangan baru. Kita boleh menyelesaikan masalah ini dengan menukar aksara pertama setiap pasangan dan menyemak sama ada ia wujud dalam tatasusunan.

Cara yang cekap untuk menyelesaikan masalah ini ialah menggunakan struktur data peta cincang.

Pernyataan Masalah - Kami mempunyai tatasusunan yang mengandungi rentetan N. Kita boleh memilih mana-mana dua rentetan daripada semua elemen tatasusunan dan menukar aksara pertama daripada dua rentetan ini. Kita perlu mengira jumlah pasangan rentetan baharu yang dijana yang tidak terdapat dalam tatasusunan.

Contoh Contoh

Input – tatasusunan[] = {"sepatutnya", "akan", "boleh"};

Output – 3

Penjelasan – Pasangan yang baru dijana boleh boleh dan wan. Pasangan lain boleh jadi siapa dan sepatutnya. Pasangan ketiga boleh san dan chould.

Input – tatasusunan[] = {"demo", "ujian"};

Output – 1

Penjelasan – Pasangan yang baru dijana yang tidak wujud dalam tatasusunan ialah temo dan dest.

Kaedah 1

Dalam kaedah ini, kami akan menggunakan dua gelung bersarang untuk mendapatkan semua pasangan elemen tatasusunan. Selepas itu kita akan menukar aksara pertama daripada dua pasangan. Seterusnya, kami akan menggunakan gelung bersarang ketiga untuk menyemak sama ada tatasusunan mengandungi pasangan itu.

Algoritma

• Tentukan pembolehubah "cnt" dan mulakan ia kepada 0 untuk menyimpan jumlah bilangan pasangan.

• Gunakan dua gelung bersarang untuk mengulangi tatasusunan rentetan dan dapatkan setiap pasangan elemen tatasusunan.

• Dapatkan pasangan semasa dua rentetan.

• Jika aksara pertama bagi dua rentetan tidak sama, tukarkannya

• Tentukan pembolehubah "isFirst" dan "isSecond" dan mulakan pembolehubah tersebut dengan false untuk menjejaki sama ada rentetan yang baru dijana terdapat dalam tatasusunan.

• Gunakan gelung bersarang ketiga untuk menyemak sama ada terdapat rentetan yang baru dijana dalam tatasusunan. Selain itu, nilai pembolehubah isFirst dan isSecond dikemas kini berdasarkan rentetan dalam tatasusunan.

• Jika tiada rentetan pertama mahupun rentetan kedua dalam tatasusunan, tingkatkan nilai 'cnt' sebanyak 1.

• Kembalikan nilai pembolehubah 'cnt'.

Contoh

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

Output

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

Kerumitan masa - O(N^3) kerana kami menggunakan tiga gelung bersarang.

Kerumitan ruang – O(1)

Kaedah 2

Dalam kaedah ini kita akan menggunakan struktur data peta untuk menyimpan semua nilai tatasusunan dalam peta. Selepas itu, kita boleh menyemak sama ada peta mengandungi rentetan yang baru dijana. Jika tidak, kita boleh menambah kiraan sebanyak 1.

Algoritma

• Takrifkan pembolehubah 'cnt'

• Gelung melalui tatasusunan rentetan dan simpan semua nilai tatasusunan dalam peta.

• Gunakan dua gelung bersarang untuk mendapatkan semua pasangan elemen tatasusunan.

• Dapatkan sepasang rentetan dan simpan dalam pembolehubah "pertama" dan "kedua".

• Jika aksara pertama bagi dua rentetan tidak sama, tukarkannya.

• Dalam peta, semak sama ada rentetan yang baru dijana disertakan. Jika tidak, tingkatkan nilai "cnt" sebanyak 1.

• Kembalikan nilai 'cnt'.

Contoh

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

Output

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

Kerumitan masa - O(N^2) kerana kami menggunakan dua gelung bersarang.

Kerumitan Angkasa – O(N) kerana kami menggunakan peta untuk menyimpan semua elemen tatasusunan.

Kami mengetahui jumlah bilangan pasangan yang baru dijana dengan menukar aksara pertama mana-mana elemen tatasusunan. Kami mengoptimumkan kod untuk kaedah kedua dari segi kerumitan masa, tetapi kod kaedah pertama lebih baik dari segi kerumitan ruang.

Atas ialah kandungan terperinci Mengira bilangan pasangan rentetan baharu yang diperoleh dengan menukar aksara pertama pasangan rentetan dalam tatasusunan yang diberikan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!