Rumah > Artikel > pembangunan bahagian belakang > 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.
Input – str = "tutorialsPoint"
Output – ‘Yes’
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’
Kami tidak boleh membahagikan rentetan kepada tiga subrentetan berdasarkan keadaan yang diberikan kerana kekerapan sebarang aksara tidak melebihi 3.
Input – str = "hhhhhhhh"
Output – ‘Yes’
Mengikut syarat yang diberikan, tiga substring boleh menjadi 'h', 'h' dan 'hhhhhh'.
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.
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().
#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; }
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.
Dalam kaedah ini, kita mula-mula menukar rentetan kepada tatasusunan aksara. Selepas itu, kami menggunakan kaedah count() untuk mengira kekerapan aksara tertentu dalam tatasusunan.
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.
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.
#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; }
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.
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!