นับสตริงย่อยด้วยอักขระตัวแรกและตัวสุดท้ายเหมือนกันใน C++

เราได้รับสตริง str เป้าหมายคือการนับจำนวนสตริงย่อยใน str ที่มีอักขระเริ่มต้นและสิ้นสุดเหมือนกัน ตัวอย่างเช่น ถ้าอินพุตเป็น "baca" สตริงย่อยจะเป็น "b", "a", "c", "a", "aca" รวม 5.

ให้เราเข้าใจด้วยตัวอย่าง

ป้อนข้อมูล − str=”abaefgf”

ผลผลิต −จำนวนสตริงย่อยที่มีอักขระตัวแรกและตัวสุดท้ายเหมือนกันคือ:9

คำอธิบาย − สตริงย่อยจะเป็น

“a”, “b”, “a”, “e” ,”f”, “g”, “f”, “aba”, “fgf”. Total 9.

ป้อนข้อมูล − str=”abcdef”

ผลผลิต −จำนวนสตริงย่อยที่มีอักขระตัวแรกและตัวสุดท้ายเหมือนกันคือ:6

คำอธิบาย − สตริงย่อยจะเป็น −

“a” , “b” , “c”, “d”, “e” ,”f”. Total 6

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

อาจมีหลายวิธีในการแก้ปัญหาที่กำหนด เช่น แนวทางไร้เดียงสาและแนวทางที่มีประสิทธิภาพ มาดูแนวทางไร้เดียงสากันก่อน เราจะส่งต่อสตริงย่อยทุกความยาวไปยังฟังก์ชัน check() หากสตริงย่อยนั้นเริ่มต้นและลงท้ายด้วยอักขระเดียวกัน ให้เพิ่มจำนวนขึ้น

• ใช้สตริง str. คำนวณความยาวเป็น str.size()

• การตรวจสอบฟังก์ชัน (สตริง str) รับสตริงย่อย str และตรวจสอบว่าอักขระตัวแรกและตัวสุดท้ายเหมือนกันหรือไม่ ( str[0]==str[length-1] ) ถ้าเป็นจริง ให้คืนค่า 1.

• ฟังก์ชัน check_Start_End(string str, int length) รับ str และความยาวเป็นอินพุต และส่งคืนค่าจำนวนสตริงย่อยของ str ที่ขึ้นต้นและลงท้ายด้วยอักขระเดียวกัน

• นับเริ่มต้นเป็น 0

• Traverse str โดยใช้ two for loops จาก i=0 ถึง i

• เราจะได้ substrings ทั้งหมดโดยใช้ substr(i,j) ทุกความยาว ส่งผ่านแต่ละสตริงย่อยเพื่อตรวจสอบ () หากคืนค่า 1 ให้นับเพิ่มขึ้น

• เมื่อสิ้นสุดการนับลูปทั้งสองจะมีสตริงย่อยของ str จำนวนหนึ่งที่มีอักขระเริ่มต้นและสิ้นสุดเหมือนกัน

• ผลตอบแทนนับเป็นผลลัพธ์ที่ต้องการ

แนวทางที่มีประสิทธิภาพ

อย่างที่เราเห็น คำตอบนั้นขึ้นอยู่กับความถี่ของอักขระแต่ละตัวในสตริงดั้งเดิม

ตัวอย่างเช่น ใน "bacba" ความถี่ของ "b" คือ 2 และสตริงย่อยรวมถึง "b" คือ "b", "bacb" และ "b"

ซึ่งก็คือ 2+1C2=3 ก่อนอื่นเราจะตรวจสอบความถี่ของอักขระแต่ละตัวและเพิ่ม ^{(ความถี่ของถ่าน+1)} C₂ .

• ใช้สตริง str. คำนวณความยาวเป็น str.size()

• ฟังก์ชัน check_Start_End(string str, int length) รับ str และความยาวเป็นอินพุต และส่งคืนค่าจำนวนสตริงย่อยของ str ที่ขึ้นต้นและลงท้ายด้วยอักขระเดียวกัน

• เริ่มนับ -0

• ใช้อาร์เรย์ arr[26] เพื่อเก็บความถี่ของอักขระแต่ละตัว

• ข้ามสตริงและความถี่การจัดเก็บ arr[str[i]='a']++

• อาร์เรย์ความถี่ในการเคลื่อนที่ arr[26] และสำหรับแต่ละความถี่ arr[i] ให้เพิ่ม arr[i]*(arr[i]+1)/2 เพื่อนับ

• ผลตอบแทนสุดท้ายนับเป็นผลลัพธ์

ตัวอย่าง (แนวทางไร้เดียงสา)

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

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

Count of substrings with same first and last characters are: 13

ตัวอย่าง (แนวทางที่มีประสิทธิภาพ)

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

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

Count of substrings with same first and last characters are: 13