Menyemak sama ada rentetan boleh dipecahkan kepada tiga subrentetan, di mana satu subrentetan ialah subrentetan daripada dua subrentetan yang lain

Dalam masalah ini, kita perlu membelah rentetan yang diberikan supaya subrentetan ketiga boleh menjadi subrentetan daripada dua substring pertama.

Mari kita fikirkan penyelesaiannya. Rentetan ketiga boleh menjadi subrentetan daripada dua rentetan pertama hanya jika dua rentetan pertama mengandungi semua aksara rentetan ketiga. Jadi, kita perlu mencari sekurang-kurangnya satu aksara dengan kekerapan lebih daripada 3 dalam rentetan yang diberikan, dan kita boleh mengambil subrentetan ketiga bagi aksara tunggal itu.

Pernyataan Masalah - Kami diberi rentetan str yang mengandungi N aksara abjad huruf kecil. Kita perlu menyemak sama ada kita boleh membahagikan rentetan kepada tiga subrentetan a, b dan c supaya subrentetan c ialah subrentetan a dan b. Cetak "ya" atau "tidak" bergantung pada sama ada 3 subrentetan boleh ditemui.

Contoh

Input –  str = "tutorialsPoint"

Output – ‘Yes’

Arahan

Di sini kita boleh membahagikan rentetan kepada "tu", "torialsPoin" dan "t". Oleh itu, rentetan ketiga ialah subrentetan daripada dua rentetan pertama.

Input –  str = "tutorials"

Output – ‘No’

Arahan

Kami tidak boleh membahagikan rentetan kepada tiga subrentetan berdasarkan keadaan yang diberikan kerana kekerapan sebarang aksara tidak melebihi 3.

Input –  str = "hhhhhhhh"

Output – ‘Yes’

Arahan

Mengikut syarat yang diberikan, tiga substring boleh menjadi 'h', 'h' dan 'hhhhhh'.

Kaedah 1

Dalam kaedah ini, kami akan menggunakan tatasusunan untuk menyimpan kekerapan setiap aksara. Selepas itu, kami akan menyemak aksara dengan kekerapan lebih besar daripada atau sama dengan 3.

Algoritma

• Langkah 1 - Tentukan tatasusunan "freq" dengan panjang bersamaan dengan 26.

• Langkah 2 - Gelung melalui rentetan untuk mengira kekerapan aksara. Dalam gelung for, naikkan nilai freq[str[i] – ‘a’]. Di sini, str[i] – ‘a’ memberikan indeks antara 0 dan 26.

• Langkah 3 - Sekarang, gelung melalui tatasusunan "freq" dan kembalikan benar jika nilai pada mana-mana indeks tatasusunan lebih besar daripada "3".

• Langkah 4 - Kembalikan benar apabila gelung ditamatkan.

• Langkah 5 - Cetak "Ya" atau "Tidak" berdasarkan nilai pulangan fungsi isSUbStringPossible().

Contoh

#include <bits/stdc++.h>
using namespace std;
// function to Check if a string can be split into 3 substrings such that one of them is a substring of the other two
string isSubStringPossible(string str, int len){

   // array to store the frequency
   int freq[26] = {0};
   
   // Iterate over the string
   for (int i = 0; i < len; i++){
   
      // count the frequency of each character
      freq[str[i] - 'a']++;
   }
   
   // Traverse the frequency array
   for (int i = 0; i < 26; i++){
   
      // If the frequency of any character is greater than or equal to 3, then return "Yes."
      if (freq[i] >= 3){
         return "Yes";
      }
   }
   
   // Otherwise
   return "No";
}
int main(){
   string str = "tutorialsPoint";
   int len = str.length();
   cout << "The given string can be splited into 3 substrings such that one of them is a substring of the other two - " << isSubStringPossible(str, len);
   return 0;
}

Output

The given string can be splited into 3 substrings such that one of them is a substring of the other two - Yes

Kerumitan masa - O(N), apabila kita mengulangi rentetan.

Kerumitan ruang - O(1) kerana kami menggunakan tatasusunan panjang tetap.

Kaedah 2

Dalam kaedah ini, kita mula-mula menukar rentetan kepada tatasusunan aksara. Selepas itu, kami menggunakan kaedah count() untuk mengira kekerapan aksara tertentu dalam tatasusunan.

Algoritma

• Langkah 1 - Buat tatasusunan saiz "len + 1", dengan "len" ialah panjang rentetan.

• Langkah 2 - Salin rentetan ke dalam tatasusunan char menggunakan kaedah strcpy().

• Langkah 3 - Gunakan gelung for untuk sejumlah 26 lelaran.

• Langkah 4 - Dalam gelung for, gunakan kaedah count() untuk mengira bilangan kejadian bagi aksara tertentu.

Kaedah

count() mengambil rujukan kepada kedudukan permulaan sebagai argumen pertama, rujukan kepada kedudukan penamat sebagai argumen kedua dan aksara sebagai argumen ketiga.

Di sini, kita perlu lulus nilai ASCII aksara sebagai parameter dan kita menggunakan I + 'a' untuk mendapatkan nilai.

• Langkah 5 - Kembalikan benar jika kaedah kiraan() mengembalikan lebih besar daripada atau sama dengan 3.

• Langkah 6 - Kembalikan palsu apabila gelung ditamatkan.

Contoh

#include <bits/stdc++.h>
using namespace std;
// function to Check if a string can be split into 3 substrings such that one of them is a substring of the other two
string isSubStringPossible(string str, int len){

   //    converting str to char array.
   char char_array[len + 1];
   
   // copy string to char array
   strcpy(char_array, str.c_str());
   
   // make 26 iterations
   for (int i = 0; i < 26; i++){
   
      // Using count() to count the occurrence of each character in the array, and return 'yes' if any character occurs more than 2 times.
      if (count(char_array, char_array + len, i + 'a') >= 2)
         return "YES";
   }
   return "NO";
}
int main(){
   string str = "tutorials";
   int len = str.length();
   cout << "The given string can be splited into 3 substrings such that one of them is a substring of the other two - " << isSubStringPossible(str, len);
   return 0;
}

Output

The given string can be splited into 3 substrings such that one of them is a substring of the other two - Yes

Kerumitan masa - O(N) kerana kaedah count() berulang ke atas tatasusunan aksara untuk mengira bilangan aksara. Juga, kaedah strcpy() mengambil masa O(N).

Kerumitan ruang - O(N) kerana kami menyimpan rentetan ke dalam tatasusunan aksara.

Kesimpulan

Kami mempelajari dua cara untuk membahagikan rentetan kepada tiga subrentetan supaya satu subrentetan boleh menjadi subrentetan dua subrentetan lain. Kod kaedah kedua lebih mudah dibaca dan mesra pemula, tetapi ia lebih mahal dari segi masa dan ruang.

Atas ialah kandungan terperinci Menyemak sama ada rentetan boleh dipecahkan kepada tiga subrentetan, di mana satu subrentetan ialah subrentetan daripada dua subrentetan yang lain. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!