Tambah urutan minimum yang diperlukan untuk menambah rentetan A untuk mendapatkan rentetan B

Dalam masalah ini, kita perlu membina str2 menggunakan urutan str1. Untuk menyelesaikan masalah ini, kita boleh mencari urutan str1 supaya ia meliputi subrentetan panjang maksimum str2. Di sini kita akan mempelajari dua cara berbeza untuk menyelesaikan masalah tersebut.

Pernyataan Masalah– Kami diberi dua tali yang berbeza panjang: str1 dan str2. Kita perlu membina str2 daripada str1 mengikut syarat berikut.

• Pilih mana-mana urutan daripada str1 dan tambahkannya pada rentetan baharu (pada mulanya kosong).

Kami perlu mengembalikan bilangan minimum operan yang diperlukan untuk membina str2, atau mencetak -1 jika str2 tidak boleh dibina.

Contoh

Masukkan – str1 = “acd”, str2 = “adc”

Output– 2

Arahan

Susunan pertama dalam

• str1 ialah "iklan". Jadi, rentetan kami boleh menjadi "iklan".

• Selepas itu, kita boleh mendapatkan jujukan "c" daripada str1 dan menambahkannya pada "ad" untuk menjadikannya "adc".

Input– str1 = "adcb", str2 = "abdca"

Output–3

Arahan

• Jujukan pertama ialah "ab" dalam str1.

• Selepas itu, kita boleh mendapatkan rentetan "dc" dan rentetan yang terhasil ialah "abdc"

• Seterusnya, kita boleh menggunakan urutan "a" untuk menjana rentetan akhir "abdca".

Kaedah 1

Dalam kaedah ini, kami akan mengulangi str1 untuk mencari berbilang urutan dan menambahkannya pada rentetan yang terhasil.

Algoritma

• Tentukan tatasusunan "arr" dengan panjang 26 dan mulakan semua elemen kepada 0 untuk menyimpan kehadiran aksara dalam str1.

• Lelaran str1 dan kemas kini nilai elemen tatasusunan mengikut nilai ASCII aksara

• Tentukan pembolehubah "terakhir" dan mulakan dengan -1 untuk menjejaki elemen terakhir yang dilawati. Selain itu, tentukan pembolehubah "cnt" dan mulakannya kepada 0 untuk menyimpan kiraan operasi.

• Mula menggunakan gelung untuk melintasi str2.

• Jika aksara semasa tiada dalam str1, kembalikan -1.

• Mulakan pembolehubah "j" dengan nilai "terakhir + 1".

• Gunakan gelung sementara untuk lelaran sehingga nilai j kurang daripada len dan str1[j] tidak sama dengan aksara

• Jika nilai 'j' lebih besar daripada 'len', kami akan melelang ke atas 'str1'. Tingkatkan nilai pembolehubah 'cnt', mulakan 'last' kepada -1 kerana kita perlu mengulangi 'str1' sekali lagi, kurangkan nilai 'I' sebanyak 1 kerana kita perlu mempertimbangkan aksara semasa sekali lagi, teruskan menggunakan 'teruskan' kata kunci Lelaran.

• Kemas kini nilai pembolehubah "terakhir" kepada "j".

• Kembalikan "cnt + 1" selepas semua lelaran gelung selesai. Di sini, kita perlu menambah "1" kepada "cnt" kerana kita tidak mempertimbangkan operasi terakhir.

Contoh

#include <iostream>
using namespace std;

// function to count the minimum number of operations required to get string str2 from subsequences of string str1.
int minOperations(string str1, string str2){
   int len = str1.length();
   // creating an array of size 26 to store the presence of characters in string str1.
   int arr[26] = {0};
   // storing the presence of characters in string str1.
   for (int i = 0; i < len; i++){
      arr[str1[i] - 'a']++;
   }
   // store the last iterated index of string str1.
   int last = -1;
   //  to store the count of operations.
   int cnt = 0;
   for (int i = 0; i < str2.length(); i++){
      char ch = str2[i];
      // if the character is not present in string str1, then return -1.
      if (arr[ch - 'a'] == 0){
         return -1;
      }
      // start iterating from the jth index of string str1 to find the character ch.
      int j = last + 1;
      while (j < len && str1[j] != ch){
          j++;
      }
      // if j is equal to the length of string str1, then increment the count, set last to -1, and decrement i.
      if (j >= len){
         cnt++;
         last = -1;
         --i;
         continue;
      }
      // set last to j.
      last = j;
   }
   // return cnt + 1 as we haven't counted the last operation.
   return cnt + 1;
}
int main(){
   string str1 = "acd", str2 = "adc";
   int operations = minOperations(str1, str2);
   cout << "Minimum number of operations required to create string B from the subsequences of the string A is: " << operations << "\n";
   return 0;
}

Output

Minimum number of operations required to create string B from the subsequences of the string A is: 2

Kerumitan masa – O(N*M), dengan N ialah panjang str2 dan M ialah panjang str1.

Kerumitan ruang - O(1) kerana kami tidak menggunakan sebarang ruang dinamik.

Kaedah 2

Dalam kaedah ini, kami akan menggunakan struktur data pemetaan dan pengumpulan untuk meningkatkan kecekapan kaedah di atas. Logik untuk menyelesaikan masalah adalah sama seperti di atas.

Algoritma

• Takrifkan "chars_mp" untuk menyimpan char -> set{} sebagai pasangan nilai kunci.

• Dalam peta, simpan set indeks di mana aksara tertentu wujud dalam rentetan str1

• Tentukan pembolehubah "terakhir" dan "cnt"

• Mula melintasi str2. Jika saiz koleksi yang mengandungi indeks aksara semasa ialah sifar, -1 dikembalikan.

• Cari had atas "terakhir" dalam set indeks aksara semasa.

• Jika had atas tidak ditemui, naikkan nilai "cnt" sebanyak 1, tetapkan "last" kepada -1, kurangkan nilai "I" sebanyak 1, dan gunakan kata kunci continue.

• Kemas kini nilai pembolehubah "terakhir".

• Selepas lelaran gelung selesai, kembalikan nilai pembolehubah 'cnt'

Contoh

#include <iostream>
#include <map> 
#include <set>
using namespace std;

// function to count the minimum number of operations required to get string str2 from subsequences of string str1.
int minOperations(string str1, string str2){
   // Length of string str1
   int len = str1.length();
   // creating the map to store the set of indices for each character in str1
   map<char, set<int>> chars_mp;
   // Iterate over the characters of str1 and store the indices of each character in the map
   for (int i = 0; i < len; i++){
      chars_mp[str1[i]].insert(i);
   }
   // store the last visited index of str1
   int last = -1;
   // Stores the required count
   int cnt = 1;
   // Iterate over the characters of str2
   for (int i = 0; i < str2.length(); i++){
      char ch = str2[i];
      // If the set of indices of str2[i] is empty, then return -1
      if (chars_mp[ch].size() == 0){
         return -1;
      }
      // If the set of indices of str2[i] is not empty, then find the upper bound of last in the set of indices of str2[i]
      // It finds the smallest index of str2[i] which is greater than last
      auto it = chars_mp[ch].upper_bound(last);
      // If the upper bound is equal to the end of the set, then increment the count and update last to -1
       if (it == chars_mp[ch].end()){
          last = -1;
          cnt++;
          // Decrement I by 1 to process the current character again
          --i;
          continue;
      }
      // Update last to the current index
      last = *it;
   }
   return cnt;
}
int main(){
   string str1 = "adcb", str2 = "abdca";
   int operations = minOperations(str1, str2);
   cout << "Minimum number of operations required to create string B from the subsequences of the string A is: " << operations << "\n";
   return 0;
}

Output

Minimum number of operations required to create string B from the subsequences of the string A is: 3

Kerumitan masa – O(N*logN), memandangkan kita mengulangi str2 dan mencari sempadan atas indeks "terakhir" dalam gelung.

Kerumitan ruang – O(N) kerana kami menggunakan peta untuk menyimpan indeks aksara.

Atas ialah kandungan terperinci Tambah urutan minimum yang diperlukan untuk menambah rentetan A untuk mendapatkan rentetan B. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!