Chúng tôi được cung cấp một chuỗi str. Mục đích là để đếm số chuỗi con trong str có cùng ký tự bắt đầu và kết thúc. Ví dụ:nếu đầu vào là “baca” thì các chuỗi con sẽ là “b”, “a”, “c”, “a”, “aca”. Tổng 5.
Hãy cho chúng tôi hiểu với các ví dụ.
Đầu vào - str =”abaefgf”
Đầu ra −Số lượng chuỗi con có cùng ký tự đầu tiên và ký tự cuối cùng là:9
Giải thích - Các chuỗi con sẽ là
“a”, “b”, “a”, “e” ,”f”, “g”, “f”, “aba”, “fgf”. Total 9.
Đầu vào - str =”abcdef”
Đầu ra −Số chuỗi con có cùng ký tự đầu tiên và ký tự cuối cùng là:6
Giải thích - Các chuỗi con sẽ -
“a” , “b” , “c”, “d”, “e” ,”f”. Total 6
Cách tiếp cận được sử dụng trong chương trình dưới đây như sau
Có thể có nhiều cách tiếp cận để giải quyết vấn đề đã cho, tức là cách tiếp cận ngây thơ và cách tiếp cận hiệu quả. Vì vậy, trước tiên chúng ta hãy xem xét cách tiếp cận ngây thơ. Chúng ta sẽ chuyển các chuỗi con của mọi độ dài vào một hàm check (). Nếu chuỗi con đó bắt đầu và kết thúc bằng cùng một ký tự thì hãy tăng số lượng.
-
Lấy chuỗi str. Tính độ dài dưới dạng str.size ().
-
Kiểm tra hàm (chuỗi str) lấy chuỗi con str và kiểm tra xem ký tự đầu tiên và ký tự cuối cùng của nó có giống nhau không. (str [0] ==str [length-1]). Nếu đúng, hãy trả về 1.
-
Hàm check_Start_End (string str, int length) lấy str và độ dài của nó làm đầu vào và trả về số lượng các chuỗi con của str bắt đầu và kết thúc bằng cùng một ký tự.
-
Lấy số lượng ban đầu là 0.
-
Traverse str bằng cách sử dụng hai vòng lặp for. Từ i =0 đến i
-
Chúng ta sẽ nhận được tất cả các chuỗi con bằng cách sử dụng substr (i, j) với tất cả các độ dài. Chuyển từng chuỗi con để kiểm tra (). Nếu nó trả về 1, số gia tăng.
-
Ở cuối cả hai số vòng lặp for sẽ có một số chuỗi con của str có cùng ký tự bắt đầu và kết thúc.
-
Số lượt trả về là kết quả mong muốn.
Cách tiếp cận hiệu quả
Như chúng ta có thể thấy, câu trả lời đó phụ thuộc vào tần suất xuất hiện của mỗi ký tự trong chuỗi gốc.
Ví dụ:trong “bacba”, tần suất của “b” là 2 và các chuỗi con bao gồm “b” là “b”, “bacb” và “b”.
Đó là 2 + 1C2 =3. Trước tiên, chúng tôi sẽ kiểm tra tần suất của từng ký tự và thêm (freq of char + 1) C 2 .
-
Lấy chuỗi str. Tính độ dài dưới dạng str.size ().
-
Hàm check_Start_End (string str, int length) lấy str và độ dài của nó làm đầu vào và trả về số lượng các chuỗi con của str bắt đầu và kết thúc bằng cùng một ký tự.
-
Lấy số đếm ban đầu là-0.
-
Lấy một mảng arr [26] để lưu trữ tần số của mỗi ký tự.
-
Chuỗi duyệt và tần số lưu trữ arr [str [i] =’a’] ++.
-
Mảng tần số quét ngang arr [26] và đối với mỗi tần số arr [i] thêm arr [i] * (arr [i] +1) / 2. Để đếm.
-
Cuối cùng, kết quả là trả về.
Ví dụ (cách tiếp cận ngây thơ)
#include <bits/stdc++.h>
using namespace std;
int check(string str){
int length = str.length();
if(str[0] == str[length-1]){
return 1;
}
}
int check_Start_End(string str, int length){
int count = 0;
for (int i = 0; i < length; i++){
for (int j = 1; j <= length-i; j++){
if (check(str.substr(i, j))){
count++;
}
}
}
return count;
}
int main(){
string str = "bcbdedfef";
int length = str.length();
cout<<"Count of substrings with same first and last characters are: "<<check_Start_End(str, length);
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of substrings with same first and last characters are: 13
Ví dụ (Phương pháp Tiếp cận Hiệu quả)
#include <bits/stdc++.h>
using namespace std;
#define maximum 26
int check_Start_End(string str, int length){
int count = 0;
int arr[maximum] = {0};
for(int i=0; i<length; i++){
arr[str[i] - 'a']++;
}
for (int i=0; i<maximum; i++){
count = count + (arr[i]*(arr[i]+1)/2);
}
return count;
}
int main(){
string str = "bcbdedfef";
int length = str.length();
cout<<"Count of substrings with same first and last characters are: "<<check_Start_End(str,
length);
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of substrings with same first and last characters are: 13